Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms

DOI10.1007/978-3-540-78773-0_46zbMath1136.68448arXiv0707.2760OpenAlexW1517042931MaRDI QIDQ5458557

Paul Bonsma, Florian Zickfeld

Publication date: 15 April 2008

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

Full work available at URL: https://arxiv.org/abs/0707.2760

Mathematics Subject Classification ID

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

Related Items

Lower bounds on the number of leaves in spanning trees, The \(k\)-leaf spanning tree problem admits a klam value of 39, Bounds of the number of leaves of spanning trees in graphs without triangles, Bounds of the number of leaves of spanning trees, Improved bounds for spanning trees with many leaves, Max-leaves spanning tree is APX-hard for cubic graphs, A new algorithm for finding trees with many leaves, An exact algorithm for the maximum leaf spanning tree problem, Spanning 3-ended trees in almost claw-free graphs, Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree, Spanning trees: A survey, The existence of spanning ended system on claw-free graphs, Spanning trees with many leaves: new lower bounds in terms of the number of vertices of degree 3 and at least 4, Spanning trees with many leaves: lower bounds in terms of the number of vertices of degree 1, 3 and at least 4, Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems, A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs

Cites Work

• Unnamed Item
• Parametrized complexity theory.
• Spanning trees with many leaves in cubic graphs
• Spanning Trees with Many Leaves
• On Linear Time Minor Tests with Depth-First Search
• Mathematical Foundations of Computer Science 2003
• A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs