Multiple-Source Shortest Paths in Embedded Graphs

DOI10.1137/120864271zbMath1276.05031arXiv1202.0314OpenAlexW2109920117MaRDI QIDQ2862202

Jeff Erickson, Sergio Cabello, Erin Wolf 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 structurestopological graph theoryparametric shortest paths

Mathematics Subject Classification ID

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

Related Items (18)

Minimum Cuts in Surface Graphs ⋮ Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time ⋮ Reconfiguration of spanning trees with degree constraints or diameter constraints ⋮ Faster shortest paths in dense distance graphs, with applications ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Topologically trivial closed walks in directed surface graphs ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ On almost Monge all scores matrices ⋮ Shortest-path queries in static networks ⋮ Unnamed Item ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Min-Cost Flow in Unit-Capacity Planar Graphs ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Notes on graph product structure theory ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable ⋮ Discrete systolic inequalities and decompositions of triangulated surfaces

This page was built for publication: Multiple-Source Shortest Paths in Embedded Graphs