Dynamically maintaining shortest path trees under batches of updates

DOI10.1007/978-3-319-03578-9_24MaRDI QIDQ2868652zbMATH OpenOpenAlexFDO

Authors Annalisa D'Andrea, Mattia D'Emidio, Stefano Leucci, Guido Proietti, Daniele Frigioni

Publication date 17 December 2013

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-03578-9_24

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Dynamic maintenance of a shortest-path tree on homogeneous batches of updates: new algorithms and experiments
• Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
• Semidynamic algorithms for maintaining single-source shortest path trees
• scientific article; zbMATH DE number 3900809
• scientific article; zbMATH DE number 871917

Cites work

• A note on two problems in connexion with graphs
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm
• Dynamic approximate all-pairs shortest paths in undirected graphs
• Dynamic multi-level overlay graphs for shortest paths
• Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
• Fully dynamic shortest paths in digraphs with arbitrary arc weights
• Hierarchical hub labelings for shortest paths
• scientific article; zbMATH DE number 871899 (Why is no real title available?)
• Maintaining shortest paths under deletions in weighted directed graphs
• On the computational complexity of dynamic graph problems
• Semidynamic algorithms for maintaining single-source shortest path trees
• Shortest Path Tree Computation in Dynamic Graphs
• Speeding up dynamic shortest-path algorithms

Cited in

(7)

• An auction-based approach for the re-optimization shortest path tree problem
• Dynamic maintenance of a shortest-path tree on homogeneous batches of updates: new algorithms and experiments
• Path-fault-tolerant approximate shortest-path trees
• Fully Dynamic 2-Hop Cover Labeling
• Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
• Shortest Path Tree Computation in Dynamic Graphs
• Maintaining longest paths incrementally

This page was built for publication: Dynamically maintaining shortest path trees under batches of updates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2868652)