Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics
Christian Wulff‐Nilsen · 2008
Lad G være en graf indlejret i L_1-planet. Stretch-faktoren for G er maksimum over alle par af forskellige knuder p og q i G af forholdet L_1^G(p,q)/L_1(p,q), hvor L_1^G(p,q) er L_1-afstanden i G mellem p og q. Vi viser, hvordan man kan finde stretch-faktoren af en vej med n knuder i O(n*(log n)^2) worst-case tid og O(n) plads, og vi nævner generaliseringer til træer og kredse, til generelle vægtede fixed orientation-metrikker og til højere dimensioner.