An efficient oracle for counting shortest paths in planar graphs

DOI10.1016/j.tcs.2022.04.002OpenAlexW4226482498MaRDI QIDQ5918687

Qian-Ping Gu, Ye Gong

Publication date: 23 May 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.04.002

zbMATH Keywords

computational studydistance oraclesoracles for counting shortest pathsVoronoi diagrams on planar graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

• Graphs

Cites Work

• Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
• Finding small simple cycle separators for 2-connected planar graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
• Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
• Shortest-path queries in static networks
• Almost optimal distance oracles for planar graphs
• Structured recursive separator decompositions for planar graphs in linear time
• Multiway Simple Cycle Separators and I/O-Efficient Algorithms for Planar Graphs
• Faster shortest-path algorithms for planar graphs
• An efficient oracle for counting shortest paths in planar graphs
• Unnamed Item
• Unnamed Item