In this paper, we study collective additive tree spanners for families of graphs enjoying special Robertson-Seymour's tree-decompositions, and demonstrate interesting consequences of obtained results. It is known that if a graph G has a multiplicative tree t-spanner, then G admits a Robertson-Seymour's tree-decomposition with bags of radius at most 「t/2(]) in G. We use this to demonstrate that there is a polynomial time algorithm that, given an n-vertex graph G admitting a multiplicative tree t-spanner, constructs a system of at most log_2 n collective additive tree O(t log n)-spanners of G. That is, with a slight increase in the number of trees and in the stretch, one can "turn" a multiplicative tree spanner into a small set of collective additive tree spanners. We extend this result by showing that, for every fixed k, there is a polynomial time algorithm that, given an n-vertex graph G admitting a multiplicative t-spanner with tree-width k - 1, constructs a system of at most k(1+log_2n) collective additive tree O(t log n)-spanners of G.
展开▼
