Multiple-source shortest paths in embedded graphs

DOI10.1137/120864271MaRDI QIDQ2862202zbMATH OpenOpenAlexFDO

Authors S. Cabello, Jeff Erickson, Erin W. Chambers

Publication date 14 November 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.0314

zbMATH Keywords

computational topologydynamic data structuresparametric shortest pathstopological graph theory

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Relations of low-dimensional topology with graph theory (57M15) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Abstract: Let G be a directed graph with n vertices and non-negative weights in its directed edges, embedded on a surface of genus g, and let f be an arbitrary face of G. We describe a randomized algorithm to preprocess the graph in O(gn log n) time with high probability, so that the shortest-path distance from any vertex on the boundary of f to any other vertex in G can be retrieved in O(log n) time. Our result directly generalizes the O(n log n)-time algorithm of Klein [SODA 2005] for multiple-source shortest paths in planar graphs. Intuitively, our preprocessing algorithm maintains a shortest-path tree as its source point moves continuously around the boundary of f. As an application of our algorithm, we describe algorithms to compute a shortest non-contractible or non-separating cycle in embedded, undirected graphs in O(g^2 n log n) time with high probability. Our high-probability time bounds hold in the worst-case for generic edge weights, or with an additional O(log n) factor for arbitrary edge weights.

Recommendations

• Multiple source shortest paths in a genus g graph
• Holiest minimum-cost paths and flows in surface graphs
• Shortest non-trivial cycles in directed surface graphs
• Multiple-source shortest paths in planar graphs
• scientific article; zbMATH DE number 6783474

Cited in

(27)

• Faster shortest paths in dense distance graphs, with applications
• On almost Monge all scores matrices
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Notes on graph product structure theory
• Topologically trivial closed walks in directed surface graphs
• Multiple source shortest paths in a genus g graph
• Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
• Min-Cost Flow in Unit-Capacity Planar Graphs
• Topologically trivial closed walks in directed surface graphs
• Shortest-path queries in static networks
• Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Minimum Cuts in Surface Graphs
• Fault-tolerant distance labeling for planar graphs
• Fault-tolerant distance labeling for planar graphs
• Reconfiguration of spanning trees with degree constraints or diameter constraints
• Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
• Approximate distance sensitivity oracles in subquadratic space
• Approximate distance sensitivity oracles in subquadratic space
• Computing shortest closed curves on non-orientable surfaces
• Finding a shortest non-zero path in group-labeled graphs
• Almost optimal exact distance oracles for planar graphs
• An almost optimal edit distance oracle
• Fault-tolerant ST-diameter oracles
• Testing whether a subgraph is convex or isometric
• Faster construction of a planar distance oracle with \(\tilde{O}(1)\) query time

This page was built for publication: Multiple-source shortest paths in embedded graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2862202)