Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
From MaRDI portal
Publication:5458557
DOI10.1007/978-3-540-78773-0_46zbMath1136.68448arXiv0707.2760OpenAlexW1517042931MaRDI QIDQ5458557
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
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)
Related Items (16)
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
This page was built for publication: Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
