Dynamically Maintaining Shortest Path Trees under Batches of Updates

DOI10.1007/978-3-319-03578-9_24zbMath1406.68071OpenAlexW2115106512MaRDI QIDQ2868652

Mattia D'Emidio, Annalisa D'Andrea, Guido Proietti, Stefano Leucci, 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 theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Path-Fault-Tolerant Approximate Shortest-Path Trees ⋮ Fully Dynamic 2-Hop Cover Labeling ⋮ An auction-based approach for the re-optimization shortest path tree problem ⋮ Dynamic Maintenance of a Shortest-Path Tree on Homogeneous Batches of Updates

Cites Work

• Unnamed Item
• A note on two problems in connexion with graphs
• Dynamic multi-level overlay graphs for shortest paths
• Semidynamic algorithms for maintaining single-source shortest path trees
• On the computational complexity of dynamic graph problems
• Speeding Up Dynamic Shortest-Path Algorithms
• Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
• Hierarchical Hub Labelings for Shortest Paths
• Fully dynamic shortest paths in digraphs with arbitrary arc weights
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
• Shortest Path Tree Computation in Dynamic Graphs
• Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm
• Maintaining shortest paths under deletions in weighted directed graphs

This page was built for publication: Dynamically Maintaining Shortest Path Trees under Batches of Updates