Additive spanners: a simple construction

TY - GEN

T1 - Additive spanners

T2 - 14th Scandinavian Symposium and Workshops on Algorithm Theory

AU - Knudsen, Mathias Bæk Tejs

N1 - Conference code: 14

PY - 2014

Y1 - 2014

N2 - We consider additive spanners of unweighted undirected graphs. Let G be a graph and H a subgraph of G. The most naïve way to construct an additive k-spanner of G is the following: As long as H is not an additive k-spanner repeat: Find a pair (u,v) ∈ H that violates the spanner-condition and a shortest path from u to v in G. Add the edges of this path to H. We show that, with a very simple initial graph H, this naïve method gives additive 6- and 2-spanners of sizes matching the best known upper bounds. For additive 2-spanners we start with H = Ø and end with O(n3/2) edges in the spanner. For additive 6-spanners we start with H containing ⌊n 1/3⌋ arbitrary edges incident to each node and end with a spanner of size O(n4/3).

AB - We consider additive spanners of unweighted undirected graphs. Let G be a graph and H a subgraph of G. The most naïve way to construct an additive k-spanner of G is the following: As long as H is not an additive k-spanner repeat: Find a pair (u,v) ∈ H that violates the spanner-condition and a shortest path from u to v in G. Add the edges of this path to H. We show that, with a very simple initial graph H, this naïve method gives additive 6- and 2-spanners of sizes matching the best known upper bounds. For additive 2-spanners we start with H = Ø and end with O(n3/2) edges in the spanner. For additive 6-spanners we start with H containing ⌊n 1/3⌋ arbitrary edges incident to each node and end with a spanner of size O(n4/3).

U2 - 10.1007/978-3-319-08404-6_24

DO - 10.1007/978-3-319-08404-6_24

M3 - Article in proceedings

SN - 978-3-319-08403-9

T3 - Lecture notes in computer science

SP - 277

EP - 281

BT - Algorithm theory – SWAT 2014

A2 - Ravi, R.

A2 - Gørtz, Inge Li

PB - Springer

Y2 - 2 June 2014 through 4 June 2014

ER -