Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
From MaRDI portal
Publication:5874499
DOI10.4230/LIPICS.ESA.2020.31OpenAlexW3081852366MaRDI QIDQ5874499FDOQ5874499
Authors: Panagiotis Charalampopoulos, Adam Karczmarz 
Publication date: 7 February 2023
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12897/pdf/LIPIcs-ESA-2020-31.pdf/
Cites Work
- Approximate distance oracles
- Algorithm Theory - SWAT 2004
- A new approach to dynamic all pairs shortest paths
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Worst-case update times for fully-dynamic all-pairs shortest paths
- An On-Line Edge-Deletion Problem
- Maintenance of a minimum spanning forest in a dynamic plane graph
- Approximate distance oracles for planar graphs with improved query time-space tradeoff
- Compact oracles for reachability and approximate distances in planar digraphs
- Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
- A new approach to incremental cycle detection and related problems
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Shortest paths in directed planar graphs with negative lengths
- Multiple-source shortest paths in planar graphs
- An \(O(n\log n)\) algorithm for maximum \(st\)-flow in a directed planar graph
- Improved algorithms for min cut and max flow in undirected planar graphs
- Incremental cycle detection, topological ordering, and strong component maintenance
- Approximate distance oracles with improved query time
- Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- On dynamic shortest paths problems
- Dynamic graph connectivity in polylogarithmic worst case time
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- Almost optimal distance oracles for planar graphs
- Structured recursive separator decompositions for planar graphs in linear time
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Title not available (Why is that?)
- Computing and Combinatorics
- Faster deterministic fully-dynamic graph connectivity
- Many distances in planar graphs
- A fully dynamic approximation scheme for shortest paths in planar graphs
- Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
- Shortest path queries in planar graphs
- Exact distance oracles for planar graphs
- Multiple-source shortest paths in embedded graphs
- Min \(st\)-cut oracle for planar graphs with near-linear preprocessing time
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- Constant query time \((1+\epsilon)\)-approximate distance oracle for planar graphs
- Title not available (Why is that?)
- More compact oracles for approximate distances in undirected planar graphs
- Approximate distance oracles with improved bounds
- Title not available (Why is that?)
- Faster approximate diameter and distance oracles in planar graphs
- Maintaining shortest paths under deletions in weighted directed graphs
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- Dynamic Plane Transitive Closure
- On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs
- Fully dynamic all-pairs shortest paths with worst-case update-time revisited
- Deterministic partially dynamic single source shortest paths for sparse graphs
- Title not available (Why is that?)
- Decremental single-source reachability in planar digraphs
- Improved bounds for shortest paths in dense distance graphs
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- New algorithms and hardness for incremental single-source shortest paths in directed graphs
- Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
- Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
- Decremental strongly-connected components and single-source reachability in near-linear time
- A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
- Holiest minimum-cost paths and flows in surface graphs
- Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
- Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
Cited In (3)
This page was built for publication: Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874499)
