Additive tree O( n)-spanners from tree breadth

DOI10.1016/J.TCS.2022.02.011MaRDI QIDQ2124229zbMATH OpenOpenAlexFDO

Authors Oliver Bendele, Dieter Rautenbach

Publication date 19 April 2022

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

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

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)

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.

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

Cites work

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

Cited in

(3)

• Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences
• Spanners for bounded tree-length graphs
• 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)