Minimum weight Euclidean (1+)-spanners

DOI10.1016/J.EJC.2024.103927MaRDI QIDQ6201907zbMATH OpenFDO

Authors Csaba D. Tóth

Publication date 26 March 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

zbMATH Keywords

integer lattice in the planespanner algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computing methodologies for image processing (68U10) Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22)

Recommendations

• Euclidean Steiner spanners: light and sparse
• Geometric Spanners for Weighted Point Sets
• Geometric spanners for weighted point sets
• Optimal Euclidean Spanners
• Optimal Euclidean spanners, really short, thin and lanky

Cites work

• scientific article; zbMATH DE number 4070353 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 1775442 (Why is no real title available?)
• scientific article; zbMATH DE number 910877 (Why is no real title available?)
• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• A note on optimal degree-three spanners of the square lattice
• A spanner for the day after
• An optimal algorithm for constructing oriented Voronoi diagrams and geograph neighborhood graphs
• Approximation of real numbers by rationals: some metric theorems
• Classes of graphs which approximate the complete Euclidean graph
• Deformable spanners and applications
• Discrepancy of Farey sequences
• Efficient construction of a bounded-degree spanner with low weight
• Euclidean Steiner spanners: light and sparse
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Fully dynamic geometric spanners
• Geometric Spanner Networks
• Geometric approximation algorithms
• Greedy spanners are optimal in doubling metrics
• Improved algorithms for constructing fault-tolerant spanners
• Improved bounds on the spanning ratio of the theta-5-graph
• Lattice spanners of low degree
• Light Euclidean Spanners with Steiner Points
• Low-light trees, and tight lower bounds for Euclidean spanners
• Lower bound for sparse Euclidean spanners
• New and improved spanning ratios for Yao graphs
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On locality-sensitive orderings and their applications
• On sparse spanners of weighted graphs
• On the spanning and routing ratios of the directed \(\Theta_6\)-graph
• Optimal Euclidean Spanners
• The Travelling Salesman Problem and Minimum Matching in the Unit Square
• The discrepancy of Farey series
• The greedy spanner is existentially optimal
• The shortest path and the shortest road through n points
• Theta-3 is connected
• Towards tight bounds on theta-graphs: more is not always better
• Truly Optimal Euclidean Spanners
• Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
• \( \delta \)-greedy \(t\)-spanner

This page was built for publication: Minimum weight Euclidean \((1+\varepsilon)\)-spanners

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