2001 | OriginalPaper | Buchkapitel
A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms
verfasst von : Valerie King, Mikkel Thorup
Erschienen in: Computing and Combinatorics
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present a simple space saving trick that applies to many previous algorithms for transitive closure and shortest paths in dynamic directed graphs. In these problems, an update can change all edges incident to a node.The basic queries on reachability and distances should be answered in constant time, but also paths should be produced in time proportional to their length. For: Transitive closure of Demetrescu and Italiano (FOCS 2000) Space reduction from O(n3) to O(n2), preserving an amortized update time of O(n2).Exact all-pairs shortest dipaths of King (FOCS 1999) Space reduction from Ō(n3) to Ō(n2vnb), preserving an amortized update time of Ō(n2vnb), where b is the maximal edge weight.Approximate all-pairs shortest dipaths of King (FOCS 1999) Space reduction from Ō(n3) to Ō(n2), preserving an amortized update time of Ō(n2). Several authors (Demetrescu and Italiano, FOCS 2000, and Brown and King, Oberwolfach 2000) had discovered techniques to give a corresponding space reduction, but these techniques could be used to show only the existence of a desired dipath, and could not be used to produce the actual path.