scientific article; zbMATH DE number 7561410

DOI10.4230/LIPIcs.ISAAC.2018.56zbMath1503.68206MaRDI QIDQ5091049

Andrew Searns, Ivona Bezáková

Publication date: 21 July 2022

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

shortest pathspath problemsseparatorscounting oracle

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Data structures (68P05)

Related Items

Fault-tolerant distance labeling for planar graphs, An efficient oracle for counting shortest paths in planar graphs, Fault-tolerant distance labeling for planar graphs, An efficient oracle for counting shortest paths in planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Approximately counting approximately-shortest paths in directed acyclic graphs
• Counting and sampling minimum cuts in genus \(g\) graphs
• Approximately counting paths and cycles in a graph
• Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
• On the solution of linear recurrence equations
• Planar graphs, negative weight edges, shortest paths, and near linear time
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Shortest path queries in planar graphs
• A separator theorem for graphs of bounded genus
• Calculating bounds on reachability and connectedness in stochastic networks
• The Complexity of Enumeration and Reliability Problems
• A Separator Theorem for Planar Graphs
• On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs
• Planar spanners and approximate shortest path queries among obstacles in the plane
• The Parameterized Complexity of Counting Problems
• Faster shortest-path algorithms for planar graphs
• Many distances in planar graphs