Computing a minimum-dilation spanning tree is NP-hard

In a geometric network G=(S,E), the graph distance between two vertices u,[email protected]?S is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which the graph distance of a pair of vertices differs from their Euclidean distance. We show that given a set S of n points with integer coordinates in the plane and a rational dilation @d>1, it is NP-hard to determine whether a spanning tree of S with dilation at most @d exists.

• Publication year

  2007

• Venue

  Computational geometry

• Publication date

  2007-01-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.comgeo.2007.12.001arXiv cs/0703023
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On Spanners of Geometric Graphs

  2009cited by this paper
• Computing Geometric Minimum-Dilation Graphs is NP-Hard

  2006cited by this paper
• Minimum dilation triangulations

  2005cited by this paper
• Experimental study of geometric t-spanners

  2005cited by this paper
• Sparse geometric graphs with small dilation

  2005cited by this paper
• Handbook of computational geometry

  2000cited by this paper
• Closest-Point Problems in Computational Geometry

  2000cited by this paper
• Spanning Trees and Spanners

  2000cited by this paper
• Angewandte Mathematik Und Informatik Universit at Zu K Oln Tree Spanners in Planar Graphs Ss Andor P. Fekete Center for Parallel Computing Universitt at Zu Kk Oln D{50923 Kk Oln Germany

  1998cited by this paper
• A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields

  1995cited by this paper
• Constructing Degree-3 Spanners with Other Sparseness Properties

  1993cited by this paper
• There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees

  1992cited by this paper
• A sparse graph almost as good as the complete graph on points inK dimensions

  1991cited by this paper
• Constructing multidimensional spanner graphs

  1991cited by this paper

• Exact Algorithms for Minimum Dilation Triangulation

  2025cites this paper
• Geometric spanners of bounded tree-width

  2024cites this paper
• Bicriteria approximation for minimum dilation graph augmentation

  2024cites this paper
• General variable neighborhood search for the minimum stretch spanning tree problem

  2022cites this paper
• Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees

  2019cites this paper
• Motion Planning and Safety for Autonomous Driving

  2019cites this paper
• On the Stretch Factor of Polygonal Chains

  2019cites this paper
• An exact algorithm for the minimum dilation triangulation problem

  2017cites this paper
• Lattice spanners of low degree

  2016cites this paper
• Algorithmic and combinatorial results on fence patrolling, polygon cutting and geometric spanners

  2016cites this paper
• Lower Bounds on the Dilation of Plane Spanners

  2015cites this paper
• Computing Minimum Dilation Spanning Trees in Geometric Graphs

  2015cites this paper
• Minimum Dilation Triangulation: Reaching Optimality Efficiently

  2014cites this paper
• Approximated algorithms for the minimum dilation triangulation problem

  2014cites this paper
• On plane geometric spanners: A survey and open problems

  2013cites this paper
• Minimum weight Euclidean t-spanner is NP-hard

  2012cites this paper
• Single-Source Dilation-Bounded Minimum Spanning Trees

  2012cites this paper
• MINIMUM DILATION GEOMETRIC SPANNING TREES

  2011cites this paper
• Improved Multi-criteria Spanners for Ad-Hoc Networks Under Energy and Distance Metrics

  2010cites this paper
• Near Optimal Multicriteria Spanner Constructions in Wireless Ad-Hoc Networks

  2009cites this paper
• Optimal Embedding into Star Metrics

  2009cites this paper
• On the dilation spectrum of paths, cycles, and trees

  2009cites this paper
• Dilation-Optimal Edge Deletion in Polygonal Cycles

  2007cites this paper
• Collection Geometric Networks and Metric Space Embeddings — Dagstuhl Seminar —

  2007cites this paper
• Minimum-Dilation Tour ( and Path ) is NP-hard

  2007cites this paper
• Computing Geometric Minimum-Dilation Graphs is NP-Hard

  2006cites this paper
• 06481 Abstracts Collection - Geometric Networks and Metric Space Embeddings

  2006cites this paper
• On Spanners of Geometric Graphs

  2006cites this paper
• Geometric dilation and halving distance

  2006cites this paper
• Sparse geometric graphs with small dilation

  2005cites this paper