Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences

DOI10.1007/978-3-642-35843-2_18MaRDI QIDQ2927646zbMATH OpenOpenAlexFDO

Authors Feodor F. Dragan, Muad Abu-Ata

Publication date 4 November 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.2506

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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. We say that a graph $G$ {em admits a system of $mu$ collective additive tree $r$-spanners} (resp., {em multiplicative tree $t$-spanners}) if there is a system $cT(G)$ of at most $mu$ spanning trees of $G$ such that for any two vertices $x,y$ of $G$ a spanning tree $TincT(G)$ exists such that $d_T(x,y)leq{d}_G(x,y)+r$ (resp., $d_T(x,y)leqtcdot{d}_G(x,y)$). When $mu=1$ one gets the notion of {em additive tree $r$-spanner} (resp., {em multiplicative tree $t$-spanner}). 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 $lceilt/2ceil$ 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 $lo{g}_{2}n$ collective additive tree $O(tlogn)$-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 if a graph $G$ admits a multiplicative $t$-spanner with tree-width $k-1$, then $G$ admits a Robertson-Seymour's tree-decomposition each bag of which can be covered with at most $k$ disks of $G$ of radius at most $lceilt/2ceil$ each. This is used to demonstrate 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+lo{g}_{2}n)$ collective additive tree $O(tlogn)$-spanners of $G$.

Recommendations

• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• Collective Additive Tree Spanners of Homogeneously Orderable Graphs
• Collective tree spanners in graphs with bounded parameters
• Collective additive tree spanners for circle graphs and polygonal graphs
• Collective tree spanners of graphs
• Algorithm Theory - SWAT 2004
• Algorithms and Computation
• Structural Information and Communication Complexity
• Collective tree spanners for unit disk graphs with applications
• Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \)

Cited in

(7)

• Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \)
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• Collective tree spanners for unit disk graphs with applications
• Algorithm Theory - SWAT 2004
• Collective Additive Tree Spanners of Homogeneously Orderable Graphs
• Algorithms and Computation
• Collective tree spanners in graphs with bounded parameters

This page was built for publication: Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2927646)