COMPUTING THE STRETCH FACTOR AND MAXIMUM DETOUR OF PATHS, TREES, AND CYCLES IN THE NORMED SPACE
DOI10.1142/S0218195912600035zbMath1251.05086OpenAlexW2046030206WikidataQ62041788 ScholiaQ62041788MaRDI QIDQ4650090
Ansgar Grüne, Teng-Kai Yu, Rolf Klein, Christian Wulff-Nilsen, Elmar Langetepe, Tien-Ching Lin, Sheung-Hung Poon, Der-Tsai Lee
Publication date: 23 November 2012
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0218195912600035
treecycledilationstretch factorspanning ratiorectilinear pathmaximum detour\(L_1\) metricweighted fixed orientation metric
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- A note on two problems in connexion with graphs
- A fast algorithm for approximating the detour of a polygonal chain.
- Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
- On Some Distance Problems in Fixed Orientations
- Flexibility of Steiner trees in uniform orientation metrics
- Geometric Spanner Networks
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Off-Line Maintenance of Planar Configurations
- Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
- On Steiner Minimal Trees with Rectilinear Distance
- An optimal real-time algorithm for planar convex hulls
- Self-approaching curves
- Curves with increasing chords
- Approximating the Stretch Factor of Euclidean Graphs
- HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES
- On Steiner’s Problem with Rectilinear Distance
- Generalized self-approaching curves
This page was built for publication: COMPUTING THE STRETCH FACTOR AND MAXIMUM DETOUR OF PATHS, TREES, AND CYCLES IN THE NORMED SPACE
