Improving the Stretch Factor of a Geometric Network by Edge Augmentation

DOI10.1137/050635675zbMath1191.68761OpenAlexW2071776560MaRDI QIDQ3614156

Mohammad Farshi, Joachim Gudmundsson, Panos Giannopoulos

Publication date: 16 March 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://research.tue.nl/nl/publications/c7dd29c9-6ba3-4c04-999d-e4a5bb302c28

zbMATH Keywords

computational geometryapproximation algorithmsgeometric networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Distance in graphs (05C12) Approximation algorithms (68W25)

Related Items (14)

On the dilation spectrum of paths, cycles, and trees ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths ⋮ IMPROVING SHORTEST PATHS IN THE DELAUNAY TRIANGULATION ⋮ DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES ⋮ Shortest paths in the plane with obstacle violations ⋮ Minimizing the continuous diameter when augmenting a geometric tree with a shortcut ⋮ Geometric path problems with violations ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees ⋮ COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD ⋮ Shortcut sets for plane Euclidean networks (extended abstract) ⋮ Computing optimal shortcuts for networks ⋮ Unnamed Item ⋮ Computing the dilation of edge-augmented graphs in metric spaces ⋮ Shortcut sets for the locus of plane Euclidean networks

This page was built for publication: Improving the Stretch Factor of a Geometric Network by Edge Augmentation