The set union problem with dynamic weighted backtracking |
| |
Authors: | Giorgio Gambosi Giuseppe F. Italiano Maurizio Talamo |
| |
Affiliation: | (1) IASI-CNR, Viale Manzoni 30, 00185 Roma, Italy;(2) Dept. of Computer Science, Columbia University, 10027 New York, NY, USA;(3) Università di Roma, Italy;(4) Dipartimento di Matematica Pura ed Applicata, Università de L'Aquila, Italy |
| |
Abstract: | We consider an extension of the set union problem, in which dynamic weighted backtracking over sequences of unions is permitted. We present a new data structure which can support each operation inO(logn) time in the worst case. We prove that this bound is tight for pointer based algorithms. Furthermore, we design a different data structure to achieve better amortized bounds. The space complexity of both our data structures isO(n). Motivations for studying this problem arise in logic programming memory management.Work partially supported by NSF Grant CCR-88-14977, by the ESPRIT II Basic Research Actions Program of the EC under contract No. 3075 (Project ALCOM), and by the Italian MURST Project Algoritmi e Strutture di Calcolo .Partially supported by an IBM Graduate Fellowship. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|