Aarhus University Seal

Optimal Solutions for the Temporal Precedence Problem

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearch

  • Gerth Stølting Brodal
  • Christos Makris, University of Patras, Greece
  • Spyros Sioutas, University of Patras, Greece
  • Athanasios K. Tsakalidis, University of Patras, Greece
  • Kosta Tsichlas, University of Patras, Greece
  • Department of Computer Science
In this paper we refer to the Temporal Precedence Problem on Pure Pointer Machines . This problem asks for the design of a data structure, maintaining a set of stored elements and supporting the following two operations: insert and precedes . The operation insert (a) introduces a new element a in the structure, while the operation precedes (a,b) returns true iff element a was inserted before element b temporally. In [11] a solution was provided to the problem with worst-case time complexity O (log log n ) per operation and O(n log log n) space, where n is the number of elements inserted. It was also demonstrated that the precedes operation has a lower bound of Ω (log log n ) for the Pure Pointer Machine model of computation. In this paper we present two simple solutions with linear space and worst-case constant insertion time. In addition, we describe two algorithms that can handle the precedes (a,b) operation in O (log log d ) time, where d is the temporal distance between the elements a and b .
Original languageEnglish
Pages (from-to)494-510
Number of pages17
Publication statusPublished - 2002

    Research areas

  • Algorithms, Computational complexity, Dynamic data structures

See relations at Aarhus University Citationformats

ID: 280826