Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
From MaRDI portal
Publication:5899451
DOI10.1016/J.JALGOR.2004.08.004zbMATH Open1120.68114OpenAlexW2126166149MaRDI QIDQ5899451FDOQ5899451
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
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
Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Data structures (68P05)
Cited In (17)
- Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time
- Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- Title not available (Why is that?)
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Determining operations affected by delay in predictive train timetables
- Title not available (Why is that?)
- Title not available (Why is that?)
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Title not available (Why is that?)
- On dynamic shortest paths problems
- A new deterministic algorithm for fully dynamic all-pairs shortest paths
- Deterministic incremental APSP with polylogarithmic update time and stretch
- Maintaining shortest paths under deletions in weighted directed graphs
- Randomization for Efficient Dynamic Graph Algorithms
- 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5899451)
