Optimal Solutions for the Temporal Precedence Problem

Gerth Stølting Brodal, Christos Makris, Spyros Sioutas, Athanasios Tsakalidis, and Kostas Tsichlas

In Algorithmica, volume 33(4), pages 494-510, 2002.

Abstract

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 Ranjan et al. a solution was provided to the problem with worst-case time complexity O(log log n) per operation and O(nlog 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.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2002. All rights reserved.

Online version

algorithmica02.pdf (220 Kb)

DOI

10.1007/s00453-002-0935-z

BIBTEX entry

@article{algorithmica02,
  author = "Gerth St{\o}lting Brodal and Christos Makris and Spyros Sioutas and Athanasios Tsakalidis and Kostas Tsichlas",
  doi = "10.1007/s00453-002-0935-z",
  issn = "0178-4617",
  journal = "Algorithmica",
  number = "4",
  pages = "494-510",
  title = "Optimal Solutions for the Temporal Precedence Problem",
  volume = "33",
  year = "2002"
}