Fully Dynamic Algorithms for Maintaining Shortest Paths Trees

✍ Scribed by Daniele Frigioni; Alberto Marchetti-Spaccamela; Umberto Nanni

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 213 KB
• Volume: 34
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1999.1048

✦ Synopsis

We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions, and weight updates of edges. The algorithms require linear space and optimal query time. The cost of the update operations depends on the class of the considered graph and on the number of the output updates, i.e., on the number of vertices that, due to an edge modification, either change the distance from the source or change the parent in the shortest paths tree. We first show that, if we deal only with updates on the Ž . weights of edges, then the update procedures require O log n worst case time per output update for several classes of graphs, as in the case of graphs with bounded genus, bounded arboricity, bounded degree, bounded treewidth, and bounded pagenumber. For general graphs with n vertices and m edges the algorithms