Compact and low delay routing labeling scheme for unit disk graphs

DOI10.1016/j.comgeo.2012.01.015zbMath1252.68216OpenAlexW1995963690MaRDI QIDQ419502

Feodor F. Dragan, Yang Xiang, Chenyu Yan

Publication date: 18 May 2012

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2012.01.015

zbMATH Keywords

balanced separatorscollective tree spannersefficient geometric graph algorithmsrouting and distance labeling schemesunit disk graphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Routing among convex polygonal obstacles in the plane ⋮ Routing in polygonal domains ⋮ Plane hop spanners for unit disk graphs: simpler and better ⋮ Routing in unit disk graphs ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ Compact Routing in Unit Disk Graphs ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Balanced line separators of unit disk graphs ⋮ Unnamed Item ⋮ On Advice Complexity of the k-server Problem under Sparse Metrics ⋮ Routing in Polygonal Domains

Cites Work

• Unit disk graphs
• Classes of graphs which approximate the complete Euclidean graph
• Geometric ad-hoc routing
• Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs
• Well-separated pair decomposition for the unit-disk graph metric and its applications
• Spanners for Geometric Intersection Graphs
• A Separator Theorem for Planar Graphs
• Distributed Computing: A Locality-Sensitive Approach
• Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Collective Tree Spanners and Routing in AT-free Related Graphs
• Collective tree spanners of graphs
• Unnamed Item

This page was built for publication: Compact and low delay routing labeling scheme for unit disk graphs