Computing the greedy spanner in linear space

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationAlgorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings)
EditorsH.L. Bodlaender, G.F. Italiano
Place of PublicationBerlin
PublisherSpringer
Pages37-48
ISBN (Print)978-3-642-40449-8
DOIs
Publication statusPublished - 2013
Event21st Annual European Symposium on Algorithms (ESA 2013) - Sophia Antipolis, France
Duration: 2 Sep 20134 Sep 2013
Conference number: 21st
http://www.informatik.uni-trier.de/~ley/db/conf/esa/esa2013.html

Publication series

NameLecture Notes in Computer Science
Volume8125
ISSN (Print)0302-9743

Conference

Conference21st Annual European Symposium on Algorithms (ESA 2013)
Abbreviated titleESA 2013
CountryFrance
CitySophia Antipolis
Period2/09/134/09/13
Internet address

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