Computing the dilation of edge-augmented graphs in metric spaces

DOI10.1016/j.comgeo.2009.03.008zbMath1220.05124OpenAlexW2126150987MaRDI QIDQ1037772

Christian Wulff-Nilsen

Publication date: 16 November 2009

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2009.03.008

zbMATH Keywords

metric spacedilationstretch factorbest shortcutedge augmentation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Fast Algorithms for Diameter-Optimally Augmenting Paths ⋮ Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees ⋮ Faster approximate diameter and distance oracles in planar graphs ⋮ Computing optimal shortcuts for networks ⋮ Shortest-path queries in static networks ⋮ Faster Approximate Diameter and Distance Oracles in Planar Graphs ⋮ Shortcut sets for the locus of plane Euclidean networks ⋮ Unnamed Item

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Finding the upper envelope of n line segments in O(n log n) time
• Geometric Spanner Networks
• More algorithms for all-pairs shortest paths in weighted graphs
• Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces
• Improving the Stretch Factor of a Geometric Network by Edge Augmentation

This page was built for publication: Computing the dilation of edge-augmented graphs in metric spaces