Computing the greedy spanner in linear space

S.P.A. Alewijnse; Q.W. Bouts; A.P. Brink, ten; K. Buchin

doi:10.1007/978-3-642-40450-4_4

Computing the greedy spanner in linear space

S.P.A. Alewijnse, Q.W. Bouts, A.P. Brink, ten, K. Buchin

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

Abstract

The greedy spanner is a high-quality spanner: its total weight, edge count and maximal degree are asymptotically optimal and in practice significantly better than for any other spanner with reasonable construction time. Unfortunately, all known algorithms that compute the greedy spanner of n points use O(n2) space, which is impractical on large instances. To the best of our knowledge, the largest instance for which the greedy spanner was computed so far has about 13,000 vertices. We present a O(n)-space algorithm that computes the same spanner for points in Rd running in O(n2 log2n) time for any fixed stretch factor and dimension. We discuss and evaluate a number of optimizations to its running time, which allowed us to compute the greedy spanner on a graph with a million vertices. To our knowledge, this is also the first algorithm for the greedy spanner with a near-quadratic running time guarantee that has actually been implemented.

Original language	English
Title of host publication	Algorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings)
Editors	H.L. Bodlaender, G.F. Italiano
Place of Publication	Berlin
Publisher	Springer
Pages	37-48
ISBN (Print)	978-3-642-40449-8
DOIs	https://doi.org/10.1007/978-3-642-40450-4_4
Publication status	Published - 2013
Event	21st Annual European Symposium on Algorithms (ESA 2013) - Sophia Antipolis, France Duration: 2 Sep 2013 → 4 Sep 2013 Conference number: 21st http://www.informatik.uni-trier.de/~ley/db/conf/esa/esa2013.html

Publication series

Name	Lecture Notes in Computer Science
Volume	8125
ISSN (Print)	0302-9743

Conference

Conference	21st Annual European Symposium on Algorithms (ESA 2013)
Abbreviated title	ESA 2013
Country/Territory	France
City	Sophia Antipolis
Period	2/09/13 → 4/09/13
Internet address	http://www.informatik.uni-trier.de/~ley/db/conf/esa/esa2013.html

Access to Document

10.1007/978-3-642-40450-4_4

Cite this

Alewijnse, S. P. A., Bouts, Q. W., Brink, ten, A. P., & Buchin, K. (2013). Computing the greedy spanner in linear space. In H. L. Bodlaender, & G. F. Italiano (Eds.), Algorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings) (pp. 37-48). (Lecture Notes in Computer Science; Vol. 8125). Springer. https://doi.org/10.1007/978-3-642-40450-4_4

@inproceedings{1b02df181fe34ecfbd12ee5bd4d10644,

title = "Computing the greedy spanner in linear space",

abstract = "The greedy spanner is a high-quality spanner: its total weight, edge count and maximal degree are asymptotically optimal and in practice significantly better than for any other spanner with reasonable construction time. Unfortunately, all known algorithms that compute the greedy spanner of n points use O(n2) space, which is impractical on large instances. To the best of our knowledge, the largest instance for which the greedy spanner was computed so far has about 13,000 vertices. We present a O(n)-space algorithm that computes the same spanner for points in Rd running in O(n2 log2n) time for any fixed stretch factor and dimension. We discuss and evaluate a number of optimizations to its running time, which allowed us to compute the greedy spanner on a graph with a million vertices. To our knowledge, this is also the first algorithm for the greedy spanner with a near-quadratic running time guarantee that has actually been implemented.",

author = "S.P.A. Alewijnse and Q.W. Bouts and {Brink, ten}, A.P. and K. Buchin",

year = "2013",

doi = "10.1007/978-3-642-40450-4_4",

language = "English",

isbn = "978-3-642-40449-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "37--48",

editor = "H.L. Bodlaender and G.F. Italiano",

booktitle = "Algorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings)",

address = "Germany",

note = "21st Annual European Symposium on Algorithms (ESA 2013), ESA 2013 ; Conference date: 02-09-2013 Through 04-09-2013",

url = "http://www.informatik.uni-trier.de/~ley/db/conf/esa/esa2013.html",

}

Alewijnse, SPA, Bouts, QW, Brink, ten, AP & Buchin, K 2013, Computing the greedy spanner in linear space. in HL Bodlaender & GF Italiano (eds), Algorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings). Lecture Notes in Computer Science, vol. 8125, Springer, Berlin, pp. 37-48, 21st Annual European Symposium on Algorithms (ESA 2013), Sophia Antipolis, France, 2/09/13. https://doi.org/10.1007/978-3-642-40450-4_4

Computing the greedy spanner in linear space. / Alewijnse, S.P.A.; Bouts, Q.W.; Brink, ten, A.P.; Buchin, K.

Algorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings). ed. / H.L. Bodlaender; G.F. Italiano. Berlin : Springer, 2013. p. 37-48 (Lecture Notes in Computer Science; Vol. 8125).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Computing the greedy spanner in linear space

AU - Alewijnse, S.P.A.

AU - Bouts, Q.W.

AU - Brink, ten, A.P.

AU - Buchin, K.

N1 - Conference code: 21st

PY - 2013

Y1 - 2013

N2 - The greedy spanner is a high-quality spanner: its total weight, edge count and maximal degree are asymptotically optimal and in practice significantly better than for any other spanner with reasonable construction time. Unfortunately, all known algorithms that compute the greedy spanner of n points use O(n2) space, which is impractical on large instances. To the best of our knowledge, the largest instance for which the greedy spanner was computed so far has about 13,000 vertices. We present a O(n)-space algorithm that computes the same spanner for points in Rd running in O(n2 log2n) time for any fixed stretch factor and dimension. We discuss and evaluate a number of optimizations to its running time, which allowed us to compute the greedy spanner on a graph with a million vertices. To our knowledge, this is also the first algorithm for the greedy spanner with a near-quadratic running time guarantee that has actually been implemented.

AB - The greedy spanner is a high-quality spanner: its total weight, edge count and maximal degree are asymptotically optimal and in practice significantly better than for any other spanner with reasonable construction time. Unfortunately, all known algorithms that compute the greedy spanner of n points use O(n2) space, which is impractical on large instances. To the best of our knowledge, the largest instance for which the greedy spanner was computed so far has about 13,000 vertices. We present a O(n)-space algorithm that computes the same spanner for points in Rd running in O(n2 log2n) time for any fixed stretch factor and dimension. We discuss and evaluate a number of optimizations to its running time, which allowed us to compute the greedy spanner on a graph with a million vertices. To our knowledge, this is also the first algorithm for the greedy spanner with a near-quadratic running time guarantee that has actually been implemented.

U2 - 10.1007/978-3-642-40450-4_4

DO - 10.1007/978-3-642-40450-4_4

M3 - Conference contribution

SN - 978-3-642-40449-8

T3 - Lecture Notes in Computer Science

SP - 37

EP - 48

BT - Algorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings)

A2 - Bodlaender, H.L.

A2 - Italiano, G.F.

PB - Springer

CY - Berlin

T2 - 21st Annual European Symposium on Algorithms (ESA 2013)

Y2 - 2 September 2013 through 4 September 2013

ER -