Sparse additive spanners for bounded tree-length graphs

DOI10.1007/978-3-540-27796-5_12MaRDI QIDQ5315220zbMATH OpenOpenAlexFDO

Authors Yon Dourisboure, Cyril Gavoille

Publication date 7 September 2005

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

Full work available at URL https://doi.org/10.1007/b98251

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Spanners for bounded tree-length graphs
• Additive sparse spanners for graphs with bounded length of largest induced cycle
• Additive spanners for k-chordal graphs
• Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \)
• Additive Tree Spanners

Cited in

(10)

• Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \)
• Tree-decompositions with bags of small diameter
• Spanners for bounded tree-length graphs
• Additive sparse spanners for graphs with bounded length of largest induced cycle
• Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences
• Additive spanners for k-chordal graphs
• Additive Tree Spanners
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• Additive graph spanners
• Collective Additive Tree Spanners of Homogeneously Orderable Graphs

This page was built for publication: Sparse additive spanners for bounded tree-length graphs

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