Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
From MaRDI portal
Publication:5874499
DOI10.4230/LIPICS.ESA.2020.31OpenAlexW3081852366MaRDI QIDQ5874499FDOQ5874499
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(nlog2 n/loglogn) 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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- 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)
