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

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) 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) Network design and communication in computer systems (68M10)

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

• scientific article; zbMATH DE number 1756017 (Why is no real title available?)
• 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
• 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

(13)

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

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)