Efficient construction of a bounded degree spanner with low weight

Sunil Arya; Michiel Staid

doi:10.1007/bfb0049396

Efficient construction of a bounded degree spanner with low weight

Sunil Arya, Michiel Staid

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

9 Citations (Scopus)

Abstract

Let S be s set of n points in IR^d and let t ˃ I be a real number. A t-spanner for 5 is a graph having the points of S as its vertices such that for any pair p, q of points there is a path between them of length at most t times the Euclidean distance between p and q. An efficient implementation of a greedy algorithm is given that constructs a t-spanner having bounded degree such that the total length of an its edges is bounded by O(log n) times the length of a minimum spanning tree for 5. The algorithm has running time O(n log^d n). Applying recent results of Das, Nazasimhan and Salowe to this t-spanner gives an O(n log^d n) time algorithm for constructing a t-spanner having bounded degree and whose total edge length is proportional to the length of a minimum spanning tree for 5. Previously, no o(n²) time algorithms were known for constructing a t-spanner of bounded degree. In the final part of the paper, an application to the problem of distance enumeration is given.

Original language	English
Title of host publication	Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings
Editors	Jan van Leeuwen
Publisher	Springer Verlag
Pages	48-59
Number of pages	12
ISBN (Print)	9783540584346
DOIs	https://doi.org/10.1007/bfb0049396
Publication status	Published - 1994
Externally published	Yes
Event	2nd Annual European Symposium on Algorithms, ESA 1994 - Utrecht, Netherlands Duration: 26 Sept 1994 → 28 Sept 1994

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	855 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2nd Annual European Symposium on Algorithms, ESA 1994
Country/Territory	Netherlands
City	Utrecht
Period	26/09/94 → 28/09/94

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1994.

Access to Document

10.1007/bfb0049396

Cite this

Arya, S., & Staid, M. (1994). Efficient construction of a bounded degree spanner with low weight. In J. van Leeuwen (Ed.), Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings (pp. 48-59). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 855 LNCS). Springer Verlag. https://doi.org/10.1007/bfb0049396

@inproceedings{9031ad4fc62345f79d521eaf61a45463,

title = "Efficient construction of a bounded degree spanner with low weight",

abstract = "Let S be s set of n points in IRd and let t ˃ I be a real number. A t-spanner for 5 is a graph having the points of S as its vertices such that for any pair p, q of points there is a path between them of length at most t times the Euclidean distance between p and q. An efficient implementation of a greedy algorithm is given that constructs a t-spanner having bounded degree such that the total length of an its edges is bounded by O(log n) times the length of a minimum spanning tree for 5. The algorithm has running time O(n logd n). Applying recent results of Das, Nazasimhan and Salowe to this t-spanner gives an O(n logd n) time algorithm for constructing a t-spanner having bounded degree and whose total edge length is proportional to the length of a minimum spanning tree for 5. Previously, no o(n2) time algorithms were known for constructing a t-spanner of bounded degree. In the final part of the paper, an application to the problem of distance enumeration is given.",

author = "Sunil Arya and Michiel Staid",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1994.; 2nd Annual European Symposium on Algorithms, ESA 1994 ; Conference date: 26-09-1994 Through 28-09-1994",

year = "1994",

doi = "10.1007/bfb0049396",

language = "English",

isbn = "9783540584346",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "48--59",

editor = "\{van Leeuwen\}, Jan",

booktitle = "Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings",

}

Arya, S & Staid, M 1994, Efficient construction of a bounded degree spanner with low weight. in J van Leeuwen (ed.), Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 855 LNCS, Springer Verlag, pp. 48-59, 2nd Annual European Symposium on Algorithms, ESA 1994, Utrecht, Netherlands, 26/09/94. https://doi.org/10.1007/bfb0049396

Efficient construction of a bounded degree spanner with low weight. / Arya, Sunil; Staid, Michiel.
Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings. ed. / Jan van Leeuwen. Springer Verlag, 1994. p. 48-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 855 LNCS).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - Efficient construction of a bounded degree spanner with low weight

AU - Arya, Sunil

AU - Staid, Michiel

PY - 1994

Y1 - 1994

N2 - Let S be s set of n points in IRd and let t ˃ I be a real number. A t-spanner for 5 is a graph having the points of S as its vertices such that for any pair p, q of points there is a path between them of length at most t times the Euclidean distance between p and q. An efficient implementation of a greedy algorithm is given that constructs a t-spanner having bounded degree such that the total length of an its edges is bounded by O(log n) times the length of a minimum spanning tree for 5. The algorithm has running time O(n logd n). Applying recent results of Das, Nazasimhan and Salowe to this t-spanner gives an O(n logd n) time algorithm for constructing a t-spanner having bounded degree and whose total edge length is proportional to the length of a minimum spanning tree for 5. Previously, no o(n2) time algorithms were known for constructing a t-spanner of bounded degree. In the final part of the paper, an application to the problem of distance enumeration is given.

AB - Let S be s set of n points in IRd and let t ˃ I be a real number. A t-spanner for 5 is a graph having the points of S as its vertices such that for any pair p, q of points there is a path between them of length at most t times the Euclidean distance between p and q. An efficient implementation of a greedy algorithm is given that constructs a t-spanner having bounded degree such that the total length of an its edges is bounded by O(log n) times the length of a minimum spanning tree for 5. The algorithm has running time O(n logd n). Applying recent results of Das, Nazasimhan and Salowe to this t-spanner gives an O(n logd n) time algorithm for constructing a t-spanner having bounded degree and whose total edge length is proportional to the length of a minimum spanning tree for 5. Previously, no o(n2) time algorithms were known for constructing a t-spanner of bounded degree. In the final part of the paper, an application to the problem of distance enumeration is given.

UR - https://openalex.org/W2109458752

UR - https://www.scopus.com/pages/publications/85013972210

U2 - 10.1007/bfb0049396

DO - 10.1007/bfb0049396

M3 - Conference Paper published in a book

SN - 9783540584346

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 48

EP - 59

BT - Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings

A2 - van Leeuwen, Jan

PB - Springer Verlag

T2 - 2nd Annual European Symposium on Algorithms, ESA 1994

Y2 - 26 September 1994 through 28 September 1994

ER -

Efficient construction of a bounded degree spanner with low weight

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this