Fully Dynamic Transitive Closure in Plane Dags with one Source and one Sink

Forfattere

  • Thore Husfeldt

DOI:

https://doi.org/10.7146/brics.v1i30.21613

Resumé

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 u to v ?' for arbitrary vertices u and v can be answered in logarithmic time. The size of the data structure and the initialisation time are linear in the number of edges.

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 Omega(log n/log log n) 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.

Downloads

Publiceret

1994-09-30

Citation/Eksport

Husfeldt, T. (1994). Fully Dynamic Transitive Closure in Plane Dags with one Source and one Sink. BRICS Report Series, 1(30). https://doi.org/10.7146/brics.v1i30.21613

Nummer

Nr. 30 (1994): RS-30 Fully Dynamic Transitive Closure in Plane Dags with one Source and one Sink

Sektion

Artikler

Licens

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

    1. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  1. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).