Additive tree O( n)-spanners from tree breadth

DOI10.1016/J.TCS.2022.02.011zbMATH Open1487.68173arXiv2002.12103OpenAlexW4213052279MaRDI QIDQ2124229FDOQ2124229

Oliver Bendele, Dieter Rautenbach

Publication date: 19 April 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: The tree breadth $mtb(G)$ of a connected graph $G$ is the smallest non-negative integer $ho$ such that $G$ has a tree decomposition whose bags all have radius at most $ho$. We show that, given a connected graph $G$ of order $n$ and size $m$, one can construct in time $O(mlogn)$ an additive tree $$-spanner of $G$, that is, a spanning subtree $T$ of $G$ in which $$ for every two vertices $u$ and $v$ of $G$. This improves earlier results of Dragan and K"{o}hler (Algorithmica 69 (2014) 884-905), who obtained a multiplicative error of the same order, and of Dragan and Abu-Ata (Theoretical Computer Science 547 (2014) 1-17), who achieved the same additive error with a collection of $O(logn)$ trees.

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

Recommendations

• Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• Structural Information and Communication Complexity
• Spanners for bounded tree-length graphs
• Additive Tree Spanners

zbMATH Keywords

additive tree spannermultiplicative tree spannertree breadthtree length

Mathematics Subject Classification ID

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

Cites Work

• Spanners for bounded tree-length graphs
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• Tree Spanners
• Collective Tree Spanners and Routing in AT-free Related Graphs
• Additive Tree Spanners
• Collective additive tree spanners for circle graphs and polygonal graphs
• A note on distance approximating trees in graphs
• Tree-decompositions with bags of small diameter
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences

Cited In (2)

• Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences
• Structural Information and Communication Complexity

This page was built for publication: Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \)

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