Improved local algorithms for spanner construction

DOI10.1016/J.TCS.2011.05.027MaRDI QIDQ714769zbMATH OpenOpenAlexFDO

Authors Iyad Kanj, Ge Xia

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

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Network design and communication in computer systems (68M10)

Recommendations

• On geometric spanners of Euclidean and unit disk graphs
• On Spanners of Geometric Graphs
• Efficient construction of low weight bounded degree planar spanner
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Degree four plane spanners: simpler and better

Cites work

• scientific article; zbMATH DE number 1947396 (Why is no real title available?)
• scientific article; zbMATH DE number 3299324 (Why is no real title available?)
• Classes of graphs which approximate the complete Euclidean graph
• Computational geometry. Algorithms and applications.
• Constructing plane spanners of bounded degree and low weight
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• Distributed Computing: A Locality-Sensitive Approach
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Geometric Spanner Networks
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On geometric spanners of Euclidean and unit disk graphs
• On plane geometric spanners: a survey and open problems
• On spanners and lightweight spanners of geometric graphs
• Plane Spanners of Maximum Degree Six
• Routing with guaranteed delivery in ad hoc wireless networks

Cited in

(8)

• Communication-efficient construction of the plane localized Delaunay graph
• Efficient construction of a bounded-degree spanner with low weight
• On geometric spanners of Euclidean and unit disk graphs
• Bounded-degree plane geometric spanners in practice
• Sigma-local graphs
• Local geometric spanners
• Simplified emanation graphs: a sparse plane spanner with Steiner points
• On bounded degree plane strong geometric spanners

This page was built for publication: Improved local algorithms for spanner construction

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