Improving the Stretch Factor of a Geometric Network by Edge Augmentation

DOI10.1137/050635675zbMath1191.68761MaRDI QIDQ3614156

Panos Giannopoulos, Mohammad Farshi, Joachim Gudmundsson

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 geometry; approximation algorithms; geometric networks

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

05C12: Distance in graphs

68W25: Approximation algorithms