EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER

DOI10.1142/S0218195904001366zbMath1093.68130OpenAlexW2100460487MaRDI QIDQ4818597

Yu Wang, Xiang-Yang Li

Publication date: 29 September 2004

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195904001366

zbMATH Keywords

planarspannerbounded degreelocalized algorithmlow weight

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (14)

Sparse hop spanners for unit disk graphs ⋮ Minimum power assignment in wireless ad hoc networks with spanner property ⋮ On plane geometric spanners: a survey and open problems ⋮ Geometric spanning trees minimizing the Wiener index ⋮ Plane hop spanners for unit disk graphs: simpler and better ⋮ Unnamed Item ⋮ On bounded degree plane strong geometric spanners ⋮ Unnamed Item ⋮ Lattice Spanners of Low Degree ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE ⋮ Lattice spanners of low degree ⋮ There are plane spanners of degree 4 and moderate stretch factor

Cites Work

• There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
• Efficient construction of a bounded-degree spanner with low weight
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS

This page was built for publication: EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER