Sublinear average-case shortest paths in weighted unit-disk graphs

DOI10.4230/LIPICS.SOCG.2021.46MaRDI QIDQ7234104zbMATH OpenFDO

Authors Adam Karczmarz, Jakub Pawlewicz, Piotr Sankowski

Publication date 27 April 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2021.46

zbMATH Keywords

shortest pathsdistance oraclesunit-disk graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• scientific article; zbMATH DE number 177800 (Why is no real title available?)
• scientific article; zbMATH DE number 1340281 (Why is no real title available?)
• scientific article; zbMATH DE number 6861957 (Why is no real title available?)
• Almost optimal distance oracles for planar graphs
• Approximate distance oracles
• Approximate shortest paths and distance oracles in weighted unit-disk graphs
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Efficient partition trees
• Highway dimension and provably efficient shortest path algorithms
• Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
• Near-optimal algorithms for shortest paths in weighted unit-disk graphs
• Object location using path separators
• Optimal partition trees
• Oriented percolation in two dimensions
• Shortest paths in Euclidean graphs
• Shortest paths in intersection graphs of unit disks
• The capacity of wireless networks

This page was built for publication: Sublinear average-case shortest paths in weighted unit-disk graphs

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