Back to Search
Start Over
An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs.
- Source :
-
Algorithmica . Aug2014, Vol. 69 Issue 4, p884-905. 22p. - Publication Year :
- 2014
-
Abstract
- A spanning tree T of a graph G is called a tree t- spanner of G if the distance between every pair of vertices in T is at most t times their distance in G. In this paper, we present an algorithm which constructs for an n-vertex m-edge unweighted graph G: For the latter result we use a new necessary condition for a graph to have a tree t-spanner: if a graph G has a tree t-spanner, then G admits a Robertson-Seymour's tree-decomposition with bags of radius at most ⌈ t/2⌉ and diameter at most t in G. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 69
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 96127575
- Full Text :
- https://doi.org/10.1007/s00453-013-9765-4