Computing Geometric Minimum-Dilation Graphs is NP-Hard

No abstract is available for this paper.

• Publication year

  2006

• Venue

  International journal of computational geometry and applications

• Publication date

  2006-09-18

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1142/S0218195910003244
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Improving the Stretch Factor of a Geometric Network by Edge Augmentation

  2008cited by this paper
• Computing a minimum-dilation spanning tree is NP-hard

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

  2007cited by this paper
• Geometric spanner networks

  2007cited by this paper
• The Geometric Dilation of Finite Point Sets

  2006cited by this paper
• Minimum-weight triangulation is NP-hard

  2006cited by this paper
• On Spanners of Geometric Graphs

  2006cited by this paper
• and Problem Complexity—Nonnumerical Algorithms and Problems;

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

  2005cited by this paper
• On the Geometric Dilation of Finite Point Sets

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

  2000cited by this paper
• Spanning Trees and Spanners

  2000influential reference
• 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
• NP-Completeness Results for Minimum Planar Spanners

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

  1995cited by this paper
• Tree Spanners

  1995cited by this paper
• NP-Completeness of Minimum Spanner Problems

  1994cited by this paper
• Hamilton Paths in Grid Graphs

  1982cited by this paper

• Multivariate Exploration of Metric Dilation

  2025cites this paper
• Exact Algorithms for Minimum Dilation Triangulation

  2025cites this paper
• Computing Oriented Spanners and their Dilation

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

  2024cites this paper
• Towards Instance-Optimal Euclidean Spanners

  2024cites this paper
• Oriented Spanners

  2023influential citation
• On path-greedy geometric spanners

  2022cites this paper
• On Constructing t -Spanner in IoT under SINRI

  2021cites this paper
• Near-Delaunay Metrics

  2021cites this paper
• Computing β-Stretch Paths in Drawings of Graphs

  2020cites this paper
• Improving the Dilation of a Metric Graph by Adding Edges

  2020cites this paper
• Algorithms for visualization in digital humanities

  2019influential citation
• SolarView: Low Distortion Radial Embedding with a Focus

  2019influential citation
• An exact algorithm for the minimum dilation triangulation problem

  2017cites this paper
• Partitioning Polygons via Graph Augmentation

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

  2015cites this paper
• Hardness Results for Computing Optimal Locally Gabriel Graphs

  2014cites this paper
• Optimal Geo-Indistinguishable Mechanisms for Location Privacy

  2014influential citation
• Mesurer la confidentialité avec des métriques de discernabilité: définitions, mécanismes et confidentialité des informations liées à la localisation. (Measuring Privacy with Distinguishability Metrics: Definitions, Mechanisms and Application to Location Privacy)

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

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

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

  2013cites this paper
• Plane Geometric Graph Augmentation: A Generic Perspective

  2013cites this paper
• Advanced Algorithm for Optimizing the Deployment Cost of Passive Optical Networks

  2013cites this paper
• Self-approaching Graphs

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

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

  2012cites this paper
• On Computing Optimal Locally Gabriel Graphs

  2011cites this paper
• MINIMUM DILATION GEOMETRIC SPANNING TREES

  2011influential citation
• Improved Multi-criteria Spanners for Ad-Hoc Networks Under Energy and Distance Metrics

  2010cites this paper
• Optimal Embedding into Star Metrics

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

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

  2009cites this paper
• Computing a minimum-dilation spanning tree is NP-hard

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

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

  2007cites this paper
• Geometric dilation and halving distance

  2006cites this paper
• On Spanners of Geometric Graphs

  2006cites this paper
• Sparse geometric graphs with small dilation

  2005cites this paper