Oracles for bounded-length shortest paths in planar graphs

DOI10.1145/1159892.1159895zbMath1321.05271OpenAlexW2068243119MaRDI QIDQ2944520

Łukasz Kowalik, Maciej Kurowski

Publication date: 2 September 2015

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1159892.1159895

zbMATH Keywords

shortest pathplanar graphdynamic environmentoraclebounded length

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (11)

Simultaneously load balancing for every p-norm, with reassignments ⋮ Adjacency queries in dynamic sparse graphs ⋮ Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries ⋮ Fast 3-coloring triangle-free planar graphs ⋮ Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs ⋮ Shortest-path queries in static networks ⋮ Hierarchical partial planarity ⋮ Localized and compact data-structure for comparability graphs ⋮ Improved Dynamic Graph Coloring ⋮ Navigating planar topologies in near-optimal space and time ⋮ Unnamed Item

This page was built for publication: Oracles for bounded-length shortest paths in planar graphs