TY - GEN

T1 - The emergence of sparse spanners and greedy well-separated pair decomposition

AU - Gao, Jie

AU - Zhou, Dengpan

PY - 2010

Y1 - 2010

N2 - A spanner graph on a set of points in ℝd provides shortest paths between any pair of points with lengths at most a constant factor of their Euclidean distance. A spanner with a sparse set of edges is thus a good candidate for network backbones, as in transportation networks and peer-to-peer network overlays. In this paper we investigate new models and aim to interpret why good spanners 'emerge' in reality, when they are clearly built in pieces by agents with their own interests and the construction is not coordinated. Our main result is to show that the following algorithm generates a (1 + ε)-spanner with a linear number of edges. In our algorithm, the points build edges at an arbitrary order. A point p will only build an edge pq if there is no existing edge p′q′ with p′ and q′ at distances no more than from 1/4(1+1/ε)·|pq| form p, q respectively. Eventually when all points finish checking edges to all other points, the resulted collection of edges forms a sparse spanner as desired. As a side product, the spanner construction implies a greedy algorithm for constructing linear-size well-separated pair decompositions that may be of interest on its own.

AB - A spanner graph on a set of points in ℝd provides shortest paths between any pair of points with lengths at most a constant factor of their Euclidean distance. A spanner with a sparse set of edges is thus a good candidate for network backbones, as in transportation networks and peer-to-peer network overlays. In this paper we investigate new models and aim to interpret why good spanners 'emerge' in reality, when they are clearly built in pieces by agents with their own interests and the construction is not coordinated. Our main result is to show that the following algorithm generates a (1 + ε)-spanner with a linear number of edges. In our algorithm, the points build edges at an arbitrary order. A point p will only build an edge pq if there is no existing edge p′q′ with p′ and q′ at distances no more than from 1/4(1+1/ε)·|pq| form p, q respectively. Eventually when all points finish checking edges to all other points, the resulted collection of edges forms a sparse spanner as desired. As a side product, the spanner construction implies a greedy algorithm for constructing linear-size well-separated pair decompositions that may be of interest on its own.

KW - Greedy algorithm

KW - Spanner

KW - Well-separated pair decomposition

UR - http://www.scopus.com/inward/record.url?scp=77954643692&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954643692&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-13731-0_6

DO - 10.1007/978-3-642-13731-0_6

M3 - Conference contribution

AN - SCOPUS:77954643692

SN - 364213730X

SN - 9783642137303

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

SP - 50

EP - 61

BT - Algorithm Theory - SWAT 2010 - 12th Scandinavian Symposium and Workshops on Algorithm Theory, Proceedings

T2 - 12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010

Y2 - 21 June 2010 through 23 June 2010

ER -