Fully Dynamic Transitive Closure in Plane Dags with one Source and one Sink Thore Husfeldt September 1994 |

## Abstract:We give an algorithm for the Dynamic Transitive Closure Problem
for planar directed acyclic graphs with one source and one sink. The graph
can be updated in logarithmic time under arbitrary edge insertions and
deletions that preserve the embedding. Queries of the form `is there a
directed path from The result enlarges the class of graphs for which a logarithmic (or even polylogarithmic) time dynamic transitive closure algorithm exists. Previously, the only algorithms within the stated resource bounds put restrictions on the topology of the graph or on the delete operation. To obtain our result, we use a new characterisation of the transitive closure in plane graphs with one source and one sink and introduce new techniques to exploit this characterisation. We also give a lower bound of on the amortised complexity of the problem in the cell probe model with logarithmic word size. This is the first dynamic directed graph problem with almost matching lower and upper bounds.
Available as |

Last modified: 2003-06-08 by webmaster.