Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths

DOI10.1016/J.JALGOR.2004.08.004MaRDI QIDQ5899451zbMATH OpenOpenAlexFDO

Authors Surender Baswana, Ramesh Hariharan, Sandeep Sen

Publication date 8 June 2007

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL http://eprints.iisc.ac.in/253/1/p117-baswana.pdf

zbMATH Keywords

graphdynamicshortest pathstransitive closureBFS tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Data structures (68P05)

Recommendations

• Maintaining shortest paths under deletions in weighted directed graphs
• Maintaining shortest paths under deletions in weighted directed graphs
• Improved Dynamic Reachability Algorithms for Directed Graphs
• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• scientific article; zbMATH DE number 6783482

Cited in

(17)

• Maintaining shortest paths under deletions in weighted directed graphs
• Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
• scientific article; zbMATH DE number 6783482 (Why is no real title available?)
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
• A new deterministic algorithm for fully dynamic all-pairs shortest paths
• Deterministic incremental APSP with polylogarithmic update time and stretch
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Approximating all-pair bounded-leg shortest path and APSP-AF in truly-subcubic time
• scientific article; zbMATH DE number 6850313 (Why is no real title available?)
• Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality
• scientific article; zbMATH DE number 1798166 (Why is no real title available?)
• Determining operations affected by delay in predictive train timetables
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Randomization for efficient dynamic graph algorithms (invited talk)
• On dynamic shortest paths problems

This page was built for publication: Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths

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