Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Standard

Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space. / Wulff-Nilsen, Christian; Grüne, Ansgar; Klein, Rolf; Langetepe, Elmar; Lee, D. T.; Lin, Tien Ching; Poon, Sheung Hung; Yu, Teng Kai.

I: International Journal of Computational Geometry and Applications, Bind 22, Nr. 1, 2012, s. 45-60.

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Harvard

Wulff-Nilsen, C, Grüne, A, Klein, R, Langetepe, E, Lee, DT, Lin, TC, Poon, SH & Yu, TK 2012, 'Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space', International Journal of Computational Geometry and Applications, bind 22, nr. 1, s. 45-60. https://doi.org/10.1142/S0218195912600035

APA

Wulff-Nilsen, C., Grüne, A., Klein, R., Langetepe, E., Lee, D. T., Lin, T. C., Poon, S. H., & Yu, T. K. (2012). Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space. International Journal of Computational Geometry and Applications, 22(1), 45-60. https://doi.org/10.1142/S0218195912600035

Vancouver

Wulff-Nilsen C, Grüne A, Klein R, Langetepe E, Lee DT, Lin TC o.a. Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space. International Journal of Computational Geometry and Applications. 2012;22(1):45-60. https://doi.org/10.1142/S0218195912600035

Author

Wulff-Nilsen, Christian ; Grüne, Ansgar ; Klein, Rolf ; Langetepe, Elmar ; Lee, D. T. ; Lin, Tien Ching ; Poon, Sheung Hung ; Yu, Teng Kai. / Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space. I: International Journal of Computational Geometry and Applications. 2012 ; Bind 22, Nr. 1. s. 45-60.

Bibtex

@article{7f059907519f48b39d716e2d50d65f91,
title = "Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space",
abstract = "The stretch factor and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and the metric space, respectively. In this paper we show that computing the stretch factor of a rectilinear path in L 1 plane has a lower bound of Ω(n log n) in the algebraic computation tree model and describe a worst-case O(σn log 2 n) time algorithm for computing the stretch factor or maximum detour of a path embedded in the plane with a weighted fixed orientation metric defined by σ < 2 vectors and a worst-case O(n log d n) time algorithm to d < 3 dimensions in L 1-metric. We generalize the algorithms to compute the stretch factor or maximum detour of trees and cycles in O(σn log d+1 n) time. We also obtain an optimal O(n) time algorithm for computing the maximum detour of a monotone rectilinear path in L 1 plane.",
keywords = "cycle, dilation, L metric, maximum detour, Rectilinear path, spanning ratio, stretch factor, tree, weighted fixed orientation metric",
author = "Christian Wulff-Nilsen and Ansgar Gr{\"u}ne and Rolf Klein and Elmar Langetepe and Lee, {D. T.} and Lin, {Tien Ching} and Poon, {Sheung Hung} and Yu, {Teng Kai}",
year = "2012",
doi = "10.1142/S0218195912600035",
language = "English",
volume = "22",
pages = "45--60",
journal = "International Journal of Computational Geometry and Applications",
issn = "0218-1959",
publisher = "World Scientific Publishing Co. Pte. Ltd.",
number = "1",

}

RIS

TY - JOUR

T1 - Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space

AU - Wulff-Nilsen, Christian

AU - Grüne, Ansgar

AU - Klein, Rolf

AU - Langetepe, Elmar

AU - Lee, D. T.

AU - Lin, Tien Ching

AU - Poon, Sheung Hung

AU - Yu, Teng Kai

PY - 2012

Y1 - 2012

N2 - The stretch factor and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and the metric space, respectively. In this paper we show that computing the stretch factor of a rectilinear path in L 1 plane has a lower bound of Ω(n log n) in the algebraic computation tree model and describe a worst-case O(σn log 2 n) time algorithm for computing the stretch factor or maximum detour of a path embedded in the plane with a weighted fixed orientation metric defined by σ < 2 vectors and a worst-case O(n log d n) time algorithm to d < 3 dimensions in L 1-metric. We generalize the algorithms to compute the stretch factor or maximum detour of trees and cycles in O(σn log d+1 n) time. We also obtain an optimal O(n) time algorithm for computing the maximum detour of a monotone rectilinear path in L 1 plane.

AB - The stretch factor and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and the metric space, respectively. In this paper we show that computing the stretch factor of a rectilinear path in L 1 plane has a lower bound of Ω(n log n) in the algebraic computation tree model and describe a worst-case O(σn log 2 n) time algorithm for computing the stretch factor or maximum detour of a path embedded in the plane with a weighted fixed orientation metric defined by σ < 2 vectors and a worst-case O(n log d n) time algorithm to d < 3 dimensions in L 1-metric. We generalize the algorithms to compute the stretch factor or maximum detour of trees and cycles in O(σn log d+1 n) time. We also obtain an optimal O(n) time algorithm for computing the maximum detour of a monotone rectilinear path in L 1 plane.

KW - cycle

KW - dilation

KW - L metric

KW - maximum detour

KW - Rectilinear path

KW - spanning ratio

KW - stretch factor

KW - tree

KW - weighted fixed orientation metric

UR - http://www.scopus.com/inward/record.url?scp=84866291833&partnerID=8YFLogxK

U2 - 10.1142/S0218195912600035

DO - 10.1142/S0218195912600035

M3 - Journal article

AN - SCOPUS:84866291833

VL - 22

SP - 45

EP - 60

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

SN - 0218-1959

IS - 1

ER -

ID: 172848699