# Optimal Solutions for the Temporal Precedence Problem

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 *i**n**s**e**r**t*(*a*) introduces a new element *a* in the structure,
while the operation *p**r**e**c**e**d**e**s*(*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*(*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 *p**r**e**c**e**d**e**s*(*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

**BIBT**_{E}X 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"
}