Routing in unit disk graphs

DOI10.1007/s00453-017-0308-2zbMath1390.68503arXiv1510.01072OpenAlexW3101316441MaRDI QIDQ1742368

Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Haim Kaplan

Publication date: 11 April 2018

Published in: Algorithmica, LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1510.01072

zbMATH Keywords

routing schemeunit disk graphwell-separated pair decomposition

Mathematics Subject Classification ID

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

Related Items (8)

Routing on heavy-path WSPD-spanners ⋮ Routing among convex polygonal obstacles in the plane ⋮ Routing in polygonal domains ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ Reachability problems for transmission graphs ⋮ Compact Routing in Unit Disk Graphs ⋮ Reachability problems for transmission graphs ⋮ Routing in Polygonal Domains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Compact and low delay routing labeling scheme for unit disk graphs
• Unit disk graphs
• New Routing Techniques and their Applications
• Geometric ad-hoc routing
• Labelling and Implicit Routing in Networks
• Geometric Spanner Networks
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
• A trade-off between space and efficiency for routing tables
• Compact routing schemes with improved stretch
• Compact oracles for reachability and approximate distances in planar digraphs
• Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications
• Routing with guaranteed delivery in ad hoc wireless networks

This page was built for publication: Routing in unit disk graphs