Improving the Stretch Factor of a Geometric Network by Edge Augmentation

DOI10.1137/050635675MaRDI QIDQ3614156zbMATH OpenOpenAlexFDO

Authors Mohammad Farshi, Panos Giannopoulos, 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

approximation algorithmscomputational geometrygeometric networks

Mathematics Subject Classification ID

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

Recommendations

• Finding the best shortcut in a geometric network
• Approximating the Stretch Factor of Euclidean Graphs
• scientific article; zbMATH DE number 1809600
• Computing the dilation of edge-augmented graphs in metric spaces
• Approximating the average stretch factor of geometric graphs

Cited in

(19)

• Computing the dilation of edge-augmented graphs in metric spaces
• Geometric path problems with violations
• Computing optimal shortcuts for networks
• Shortest paths in the plane with obstacle violations
• Minimizing the continuous diameter when augmenting a geometric tree with a shortcut
• Shortcut sets for the locus of plane Euclidean networks
• Fast algorithms for diameter-optimally augmenting paths
• Computing geometric minimum-dilation graphs is NP-hard
• Shortcut sets for plane Euclidean networks (extended abstract)
• Shortest paths in the plane with obstacle violations
• IMPROVING SHORTEST PATHS IN THE DELAUNAY TRIANGULATION
• Dilation-optimal edge deletion in polygonal cycles
• Finding the best shortcut in a geometric network
• Fast algorithms for diameter-optimally augmenting paths and trees
• Improving the Dilation of a Metric Graph by Adding Edges
• Improving the dilation of a metric graph by adding edges
• Bicriteria approximation for minimum dilation graph augmentation
• Multivariate exploration of metric dilation
• On the dilation spectrum of paths, cycles, and trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3614156)