A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs

DOI10.1007/978-3-540-77918-6_15zbMath1130.68311OpenAlexW1547284637MaRDI QIDQ5443382

Cristina G. Fernandes, Martin Matamala, José R. Correa, 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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (8)

Complexity of the maximum leaf spanning tree problem on planar and regular graphs ⋮ Improved bounds for spanning trees with many leaves ⋮ Max-leaves spanning tree is APX-hard for cubic graphs ⋮ Spanning trees: A survey ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms ⋮ A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs ⋮ Leafy spanning arborescences in DAGs

Cites Work

• Constructing full spanning trees for cubic graphs
• A short note on the approximability of the maximum leaves spanning tree problem
• Spanning trees with many leaves in cubic graphs
• Spanning Trees with Many Leaves
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Unnamed Item
• Unnamed Item

This page was built for publication: A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs