TY - GEN

T1 - Tree spanners for subgraphs and related tree covering problems

AU - Handke, Dagmar

AU - Kortsarz, Guy

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.

PY - 2000

Y1 - 2000

N2 - For any fixed parameter k fi 1, a tree k-spanner of a graph G is a spanning tree T in G such that the distance between every pair of vertices in T is at most k times their distance in G. In this paper, we generalize on this very restrictive concept, and introduce Steiner tree k-spanners: We are given an input graph consisting of terminals and Steiner vertices, and we are now looking for a tree k-spanner that spans all terminals. The complexity status of deciding the existence of a Steiner tree k- spanner is easy for some k: it is NP-hard for k fi 4, and it is in P for k = 1. For the case k = 2, we develop a model in terms of an equivalent tree covering problem, and use this to show NP-hardness. By showing the NP-hardness also for the case k = 3, the complexity results for all k are complete. We also consider the problem of finding a smallest Steiner tree k-spanner (if one exists at all). For any arbitrary k fi 2, we prove that we cannot hope to find eficiently a Steiner tree k-spanner that is closer to the smallest one than within a logarithmic factor. We conclude by discussing some problems related to the model for the case k = 2.

AB - For any fixed parameter k fi 1, a tree k-spanner of a graph G is a spanning tree T in G such that the distance between every pair of vertices in T is at most k times their distance in G. In this paper, we generalize on this very restrictive concept, and introduce Steiner tree k-spanners: We are given an input graph consisting of terminals and Steiner vertices, and we are now looking for a tree k-spanner that spans all terminals. The complexity status of deciding the existence of a Steiner tree k- spanner is easy for some k: it is NP-hard for k fi 4, and it is in P for k = 1. For the case k = 2, we develop a model in terms of an equivalent tree covering problem, and use this to show NP-hardness. By showing the NP-hardness also for the case k = 3, the complexity results for all k are complete. We also consider the problem of finding a smallest Steiner tree k-spanner (if one exists at all). For any arbitrary k fi 2, we prove that we cannot hope to find eficiently a Steiner tree k-spanner that is closer to the smallest one than within a logarithmic factor. We conclude by discussing some problems related to the model for the case k = 2.

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

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

U2 - 10.1007/3-540-40064-8_20

DO - 10.1007/3-540-40064-8_20

M3 - Conference contribution

AN - SCOPUS:84958817764

SN - 3540411836

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

SP - 206

EP - 217

BT - Graph-Theoretic Concepts in Computer Science - 26th International Workshop, WG 2000 Konstanz, Germany, June 15-17, 2000 Proceedings

A2 - Brandes, Ulrik

A2 - Wagner, Dorothea

PB - Springer Verlag

T2 - 26th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2000

Y2 - 15 June 2000 through 17 June 2000

ER -