Improved local algorithms for spanner construction

DOI10.1016/j.tcs.2011.05.027zbMath1247.68019OpenAlexW2179704896MaRDI QIDQ714769

Ge Xia, Iyad A. Kanj

Publication date: 11 October 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.027

zbMATH Keywords

Delaunay triangulationsspanners

Mathematics Subject Classification ID

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)

Related Items

On bounded degree plane strong geometric spanners

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On plane geometric spanners: a survey and open problems
• Constructing plane spanners of bounded degree and low weight
• Classes of graphs which approximate the complete Euclidean graph
• On Spanners and Lightweight Spanners of Geometric Graphs
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Geometric Spanner Networks
• Plane Spanners of Maximum Degree Six
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Distributed Computing: A Locality-Sensitive Approach
• Routing with guaranteed delivery in ad hoc wireless networks