Spanning ratio and maximum detour of rectilinear paths in the L _1 plane

DOI10.1007/978-3-642-17514-5_11MaRDI QIDQ3060767zbMATH OpenOpenAlexWikidataFDO

Authors Ansgar Grüne, Tien-Ching Lin, Teng-Kai Yu, Rolf Klein, Elmar Langetepe, Sheung-Hung Poon, Der-Tsai Lee

Publication date 9 December 2010

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17514-5_11

zbMATH Keywords

\(L _{1}\) metricdilationManhattan planemaximum detourrectilinear pathspanning ratio

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space
• scientific article; zbMATH DE number 2086390
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• scientific article; zbMATH DE number 5542484
• Computing the Maximum Detour of a Plane Graph in Subquadratic Time

Cited in

(4)

• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• scientific article; zbMATH DE number 5542484 (Why is no real title available?)
• Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space
• scientific article; zbMATH DE number 2086390 (Why is no real title available?)

This page was built for publication: Spanning ratio and maximum detour of rectilinear paths in the \(L _{1}\) plane

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