Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics

Christian Wulff-Nilsen

Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics

Datalogisk Institut

Abstract

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.

Originalsprog	Engelsk
Titel	Proceedings of the 20th Annual Canadian Conference on Computational Geometry - CCCG 2008 : August 13-15, McGill University, Montréal, Québec, Canada
Antal sider	4
Forlag	CCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada
Publikationsdato	2008
Sider	59-62
Status	Udgivet - 2008
Begivenhed	Canadian Conference on Computational Geometry - Montreal, Canada Varighed: 13 aug. 2008 → 15 aug. 2008 Konferencens nummer: 20

Konference

Konference	Canadian Conference on Computational Geometry
Nummer	20
Land/Område	Canada
By	Montreal
Periode	13/08/2008 → 15/08/2008

Adgang til dokumentet

Citationsformater

Wulff-Nilsen, C. (2008). Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics. I Proceedings of the 20th Annual Canadian Conference on Computational Geometry - CCCG 2008: August 13-15, McGill University, Montréal, Québec, Canada (s. 59-62). CCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada. http://www.cccg.ca/proceedings/2008/out_N_N.pdf

Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics. / Wulff-Nilsen, Christian.

Proceedings of the 20th Annual Canadian Conference on Computational Geometry - CCCG 2008: August 13-15, McGill University, Montréal, Québec, Canada. CCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada, 2008. s. 59-62.

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Wulff-Nilsen, C 2008, Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics. i Proceedings of the 20th Annual Canadian Conference on Computational Geometry - CCCG 2008: August 13-15, McGill University, Montréal, Québec, Canada. CCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada, s. 59-62, Canadian Conference on Computational Geometry, Montreal, Canada, 13/08/2008. <http://www.cccg.ca/proceedings/2008/out_N_N.pdf>

@inproceedings{1cef7590de5311ddb5fc000ea68e967b,

title = "Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics",

abstract = "Let G be a graph embedded in the L_1-plane. The stretch factor of G is the maximum over all pairs of distinct vertices p and q of G of the ratio L_1^G(p,q)/L_1(p,q), where L_1^G(p,q) is the L_1-distance in G between p and q. We show how to compute the stretch factor of an n-vertex path in O(n*(log n)^2) worst-case time and O(n) space and we mention generalizations to trees and cycles, to general weighted fixed orientation metrics, and to higher dimensions.",

author = "Christian Wulff-Nilsen",

year = "2008",

language = "English",

pages = "59--62",

booktitle = "Proceedings of the 20th Annual Canadian Conference on Computational Geometry - CCCG 2008",

publisher = "CCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada",

note = "Canadian Conference on Computational Geometry ; Conference date: 13-08-2008 Through 15-08-2008",

}

TY - GEN

T1 - Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics

AU - Wulff-Nilsen, Christian

N1 - Conference code: 20

PY - 2008

Y1 - 2008

N2 - Let G be a graph embedded in the L_1-plane. The stretch factor of G is the maximum over all pairs of distinct vertices p and q of G of the ratio L_1^G(p,q)/L_1(p,q), where L_1^G(p,q) is the L_1-distance in G between p and q. We show how to compute the stretch factor of an n-vertex path in O(n*(log n)^2) worst-case time and O(n) space and we mention generalizations to trees and cycles, to general weighted fixed orientation metrics, and to higher dimensions.

AB - Let G be a graph embedded in the L_1-plane. The stretch factor of G is the maximum over all pairs of distinct vertices p and q of G of the ratio L_1^G(p,q)/L_1(p,q), where L_1^G(p,q) is the L_1-distance in G between p and q. We show how to compute the stretch factor of an n-vertex path in O(n*(log n)^2) worst-case time and O(n) space and we mention generalizations to trees and cycles, to general weighted fixed orientation metrics, and to higher dimensions.

M3 - Article in proceedings

SP - 59

EP - 62

BT - Proceedings of the 20th Annual Canadian Conference on Computational Geometry - CCCG 2008

PB - CCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada

T2 - Canadian Conference on Computational Geometry

Y2 - 13 August 2008 through 15 August 2008

ER -

Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater