Compact and low delay routing labeling scheme for unit disk graphs

DOI10.1016/J.COMGEO.2012.01.015MaRDI QIDQ419502zbMATH OpenOpenAlexFDO

Authors Chenyu Yan, Feodor F. Dragan, Yang Xiang

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

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) 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)

Recommendations

• Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs
• Collective tree spanners for unit disk graphs with applications
• Plane hop spanners for unit disk graphs: simpler and better

Cites work

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

Cited in

(15)

• Routing among convex polygonal obstacles in the plane
• Routing in polygonal domains
• Plane hop spanners for unit disk graphs: simpler and better
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• On advice complexity of the k-server problem under sparse metrics
• Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs
• On the advice complexity of the \(k\)-server problem under sparse metrics
• scientific article; zbMATH DE number 7236428 (Why is no real title available?)
• Routing in polygonal domains
• Balanced line separators of unit disk graphs
• Compact Routing in Unit Disk Graphs
• Routing among convex polygonal obstacles in the plane
• Shortest path separators in unit disk graphs
• A QPTAS for facility location on unit disk graphs
• Routing among convex polygonal obstacles in the plane using a simplified domain

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

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