Improved local algorithms for spanner construction

DOI10.1016/J.TCS.2011.05.027zbMATH Open1247.68019OpenAlexW2179704896MaRDI QIDQ714769FDOQ714769

Ge Xia, Iyad 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

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

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)

Cites Work

• Geometric Spanner Networks
• Distributed Computing: A Locality-Sensitive Approach
• Title not available (Why is that?)
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Routing with guaranteed delivery in ad hoc wireless networks
• 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
• Plane Spanners of Maximum Degree Six
• On plane geometric spanners: a survey and open problems
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• Title not available (Why is that?)
• Constructing plane spanners of bounded degree and low weight
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (3)

• Efficient construction of a bounded-degree spanner with low weight
• Bounded-degree plane geometric spanners in practice
• 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)