2012/07/10 by Feodor F. Dragan, Dragan, Feodor F., Muad Abu‐Ata +1 · 1 citation
Computer Science · Materials Science · Mathematics · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Metric Geometry (math.MG) #Nanocluster Synthesis and Applications #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1207.2506
openalex publication_date 2012/07/10 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
In this paper, we study collective additive tree spanners for families of\ngraphs enjoying special Robertson-Seymour's tree-decompositions, and\ndemonstrate interesting consequences of obtained results. We say that a graph\nG em admits a system of \μ collective additive tree r-spanners\n(resp., em multiplicative tree t-spanners) if there is a system cT(G)\nof at most \μ spanning trees of G such that for any two vertices x,y of\nG a spanning tree T\∈ cT(G) exists such that dT(x,y)\≤ dG(x,y)+r\n(resp., dT(x,y)\≤ t\⋅ dG(x,y)). When \μ=1 one gets the notion of\n em additive tree r-spanner (resp., em multiplicative tree t-spanner).\nIt is known that if a graph G has a multiplicative tree t-spanner, then G\nadmits a Robertson-Seymour's tree-decomposition with bags of radius at most\n lceilt/2 rceil in G. We use this to demonstrate that there is a\npolynomial time algorithm that, given an n-vertex graph G admitting a\nmultiplicative tree t-spanner, constructs a system of at most \log2 n\ncollective additive tree O(t\log n)-spanners of G. That is, with a slight\nincrease in the number of trees and in the stretch, one can "turn" a\nmultiplicative tree spanner into a small set of collective additive tree\nspanners. We extend this result by showing that if a graph G admits a\nmultiplicative t-spanner with tree-width k-1, then G admits a\nRobertson-Seymour's tree-decomposition each bag of which can be covered with at\nmost k disks of G of radius at most lceilt/2 rceil each. This is used\nto demonstrate that, for every fixed k, there is a polynomial time algorithm\nthat, given an n-vertex graph G admitting a multiplicative t-spanner with\ntree-width k-1, constructs a system of at most k(1+ \log2 n) collective\nadditive tree O(t\log n)-spanners of G.\n