An exact algorithm for the minimum dilation triangulation problem
From MaRDI portal
Publication:1679486
DOI10.1007/s10898-017-0517-xzbMath1381.90092OpenAlexW2605639086MaRDI QIDQ1679486
Sattar Sattari, Mohammad A. Izadi
Publication date: 9 November 2017
Published in: Journal of Global Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10898-017-0517-x
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
Related Items
An exact algorithm for the minimum dilation triangulation problem, Upper bounds for minimum dilation triangulation in two special cases, An improved upper bound on dilation of regular polygons
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On degrees in random triangulations of point sets
- Delaunay graphs are almost as good as complete graphs
- Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
- Computing a minimum-dilation spanning tree is NP-hard
- An exact algorithm for the minimum dilation triangulation problem
- There are planar graphs almost as good as the complete graph
- On stable line segments in all triangulations of a planar point set
- A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation
- The Stretch Factor of the Delaunay Triangulation Is Less than 1.998
- Geometric Spanner Networks
- COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD
- TSPLIB—A Traveling Salesman Problem Library
- The computational geometry algorithms library CGAL
- Lower Bounds on the Dilation of Plane Spanners