Improved bounds for spanning trees with many leaves

DOI10.1016/j.disc.2011.11.043zbMath1238.05053OpenAlexW2058827179MaRDI QIDQ409458

Paul Bonsma, Florian Zickfeld

Publication date: 13 April 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2011.11.043

zbMATH Keywords

lower boundspanning treemaximum number of leaves

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Related Items (7)

The \(k\)-leaf spanning tree problem admits a klam value of 39 ⋮ Flexible list colorings in graphs with special degeneracy conditions ⋮ A Simple 2-Approximation for Maximum-Leaf Spanning Tree ⋮ Spanning trees with few non-leaves ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Flexible List Colorings in Graphs with Special Degeneracy Conditions ⋮ Connected Domination

Cites Work

• Unnamed Item
• Unnamed Item
• A new algorithm for finding trees with many leaves
• Spanning trees in graphs of minimum degree 4 or 5
• Parametrized complexity theory.
• Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems
• Spanning trees with many leaves in cubic graphs
• A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
• Spanning Trees with Many Leaves
• Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Connected Domination and Spanning Trees with Many Leaves
• Mathematical Foundations of Computer Science 2003
• A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
• Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
• Spanning trees with many leaves

This page was built for publication: Improved bounds for spanning trees with many leaves