Improved greedy algorithms for constructing sparse geometric spanners

DOI10.1007/3-540-44985-X_28MaRDI QIDQ2721991zbMATH OpenFDO

Authors Joachim Gudmundsson, Giri Narasimhan, Christos Levcopoulos

Publication date 11 July 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-44985-X_28

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Nonnumerical algorithms (68W05)

Recommendations

• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• Efficient construction of a bounded-degree spanner with low weight
• Generating sparse spanners for weighted graphs
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS

Cited in

(16)

• Geometric spanners in the MapReduce model
• On Euclidean vehicle routing with allocation
• On path-greedy geometric spanners
• An optimal algorithm for computing angle-constrained spanners
• An optimal algorithm for computing angle-constrained spanners
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• The emergence of sparse spanners and greedy well-separated pair decomposition
• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
• Generating sparse spanners for weighted graphs
• Experimental study of geometric \(t\)-spanners
• I/O-Efficiently Pruning Dense Spanners
• STACS 2005
• On dynamic shortest paths problems
• A simple and efficient method for accelerating construction of the gap-greedy spanner
• Minimum power assignment in wireless ad hoc networks with spanner property

This page was built for publication: Improved greedy algorithms for constructing sparse geometric spanners

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