A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
From MaRDI portal
Publication:5443382
DOI10.1007/978-3-540-77918-6_15zbMath1130.68311MaRDI QIDQ5443382
Martin Matamala, José R. Correa, Cristina G. Fernandes, Yoshiko Wakabayashi
Publication date: 20 February 2008
Published in: Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-77918-6_15
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs, Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms, Improved bounds for spanning trees with many leaves, Max-leaves spanning tree is APX-hard for cubic graphs, Spanning trees: A survey
Cites Work