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

DOI10.1016/j.jalgor.2004.08.004zbMath1120.68114OpenAlexW2126166149MaRDI QIDQ5899451

Sandeep Sen, Surender Baswana, Ramesh Hariharan

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

dynamicgraphshortest pathstransitive closureBFS tree

Mathematics Subject Classification ID

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

Related Items (11)

Determining operations affected by delay in predictive train timetables ⋮ Unnamed Item ⋮ On dynamic shortest paths problems ⋮ 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 ⋮ Randomization for Efficient Dynamic Graph Algorithms ⋮ Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs ⋮ Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths

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