Single-source shortest paths and strong connectivity in dynamic planar graphs

DOI10.1016/j.jcss.2021.09.008zbMath1485.68175OpenAlexW3204093578MaRDI QIDQ2051854

Adam Karczmarz, Panagiotis Charalampopoulos

Publication date: 25 November 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12897/

zbMATH Keywords

planar graphsstrong connectivitydynamic graph algorithmssingle-source shortest paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Signed and weighted graphs (05C22)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On dynamic shortest paths problems
• A fully dynamic approximation scheme for shortest paths in planar graphs
• Separator based sparsification. I: Planarity testing and minimum spanning trees
• Faster approximate diameter and distance oracles in planar graphs
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs
• Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization
• Multiple-Source Shortest Paths in Embedded Graphs
• Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
• Approximate Distance Oracles with Improved Bounds
• Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance
• Shortest path queries in planar graphs
• An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
• Constant Query Time $$(1+\epsilon )$$ -Approximate Distance Oracle for Planar Graphs
• Dynamic Plane Transitive Closure
• Approximate distance oracles
• Worst-case update times for fully-dynamic all-pairs shortest paths
• Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• An On-Line Edge-Deletion Problem
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
• 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
• Fully Dynamic Connectivity in O(log n(log log n)²) Amortized Expected Time
• Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
• Min st -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
• A New Approach to Incremental Cycle Detection and Related Problems
• Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications
• Decremental single-source reachability in planar digraphs
• 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
• Fully-dynamic planarity testing in polylogarithmic time
• Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
• Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
• Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
• Almost optimal distance oracles for planar graphs
• 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
• Exact Distance Oracles for Planar Graphs with Failing Vertices
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• Algorithm Theory - SWAT 2004
• Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
• Deterministic decremental single source shortest paths: beyond the o(mn) bound
• Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
• Improved algorithms for min cut and max flow in undirected planar graphs
• A new approach to dynamic all pairs shortest paths
• Compact oracles for reachability and approximate distances in planar digraphs
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Structured recursive separator decompositions for planar graphs in linear time
• Approximate Distance Oracles with Improved Query Time
• More Compact Oracles for Approximate Distances in Undirected Planar Graphs
• Dynamic graph connectivity in polylogarithmic worst case time
• Faster Deterministic Fully-Dynamic Graph Connectivity
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
• Many distances in planar graphs

This page was built for publication: Single-source shortest paths and strong connectivity in dynamic planar graphs