Advertisement
Published in:
2018 | OriginalPaper | Chapter
Tree t-Spanners of a Graph: Minimizing Maximum Distances Efficiently
Authors : Fernanda Couto, Luís Felipe I. Cunha
Published in: Combinatorial Optimization and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
A tree t-spanner of a graph G is a spanning subtree T in which the distance between any two adjacent vertices of G is at most t. The smallest t for which G has a tree t-spanner is the tree stretch index. The problem of determining the tree stretch index has been studied by: establishing lower and upper bounds, based, for instance, on the girth value and on the minimum diameter spanning tree problem, respectively; and presenting some classes for which t is a tight value. Moreover, in 1995, the computational complexities of determining whether \(t = 2\) or \(t \ge 4\) were settled to be polynomially time solvable and NP-complete, respectively, while deciding if \(t = 3\) still remains an open problem.
With respect to the computational complexity aspect of this problem, we present an inconsistence on the sufficient condition of tree 2-spanner admissible graphs. Moreover, while dealing with operations in graphs, we provide optimum tree t-spanners for 2 cycle-power graphs and for prism graphs, which are obtained from 2 cycle-power graphs after removing a perfect matching. Specifically, the stretch indexes for both classes are far from their girth’s natural lower bounds, and surprisingly, the parameter does not change after such a matching removal. We also present efficient strategies to obtain optimum tree t-spanners considering threshold graphs, split graphs, and generalized octahedral graphs. With this last result in addition to vertices addition operations and the tree decomposition of a cograph, we are able to present the stretch index for cographs.