Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \)

DOI10.1016/j.tcs.2022.02.011zbMath1487.68173arXiv2002.12103OpenAlexW4213052279MaRDI QIDQ2124229

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

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

Cites Work

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

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