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

Full work available at URL https://doi.org/10.1016/J.EJC.2024.103927

zbMATH Keywords

integer lattice in the planespanner algorithm

Mathematics Subject Classification ID

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

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

• \( \delta \)-greedy \(t\)-spanner
• 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 approximation algorithms
• Geometric Spanner Networks
• Greedy spanners are optimal in doubling metrics
• 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?)
• 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 _6-graph
• Optimal Euclidean Spanners
• The discrepancy of Farey series
• The greedy spanner is existentially optimal
• The shortest path and the shortest road through n points
• The Travelling Salesman Problem and Minimum Matching in the Unit Square
• 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

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)