Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications

DOI10.1137/S0097539703436357zbMath1086.68146MaRDI QIDQ5700574

No author found.

Publication date: 28 October 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmwell-separated pair decompositionunit-disk graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (10)

Routing on heavy-path WSPD-spanners ⋮ Reverse shortest path problem for unit-disk graphs ⋮ Reverse shortest path problem in weighted unit-disk graphs ⋮ An optimal algorithm for \(L_1\) shortest paths in unit-disk graphs ⋮ On reverse shortest paths in geometric proximity graphs ⋮ Near-optimal algorithms for shortest paths in weighted unit-disk graphs ⋮ Routing in unit disk graphs ⋮ Unnamed Item ⋮ Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs. ⋮ Shortest paths in intersection graphs of unit disks

This page was built for publication: Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications