Standard
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. p. 59-62.
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Wulff-Nilsen, C 2008,
Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics. in
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, pp. 59-62, Canadian Conference on Computational Geometry, Montreal, Canada,
13/08/2008. <
http://www.cccg.ca/proceedings/2008/out_N_N.pdf>
APA
Wulff-Nilsen, C. (2008).
Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics. In
Proceedings of the 20th Annual Canadian Conference on Computational Geometry - CCCG 2008: August 13-15, McGill University, Montréal, Québec, Canada (pp. 59-62). CCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada.
http://www.cccg.ca/proceedings/2008/out_N_N.pdf
Vancouver
Wulff-Nilsen C. Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics. In 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. p. 59-62
Author
Wulff-Nilsen, Christian. / Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics. 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. pp. 59-62
Bibtex
@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 = "null ; Conference date: 13-08-2008 Through 15-08-2008",
}
RIS
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
Y2 - 13 August 2008 through 15 August 2008
ER -
