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 (3)
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
This page was built for publication: An exact algorithm for the minimum dilation triangulation problem
