CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES

DOI10.1142/S0129054196000105MaRDI QIDQ4886312zbMATH OpenOpenAlexFDO

Authors Paul J. Heffernan, Gautam K. Das

Publication date 26 November 1996

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

\(t\)-spanner

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Approximating Euclidean distances by small degree graphs
• scientific article; zbMATH DE number 1617269
• Efficient construction of a bounded-degree spanner with low weight

Cited in

(17)

• Degree-bounded minimum spanning trees
• Approximating Euclidean distances by small degree graphs
• Euclidean spanner graphs with degree four
• There are plane spanners of degree 4 and moderate stretch factor
• Lattice spanners of low degree
• Lattice spanners of low degree
• On plane geometric spanners: a survey and open problems
• On bounded degree plane strong geometric spanners
• A note on optimal degree-three spanners of the square lattice
• Lower bounds on the dilation of plane spanners
• Lower bounds on the dilation of plane spanners
• A unified framework for light spanners
• Bounded-degree plane geometric spanners in practice
• A unified framework of light spanners. I: Fast (yet optimal) constructions
• Geometric spanners of bounded tree-width
• Sparse geometric graphs with small dilation
• Computing a minimum-dilation spanning tree is NP-hard

This page was built for publication: CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES

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