A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
From MaRDI portal
Publication:5302044
DOI10.1007/978-3-540-92248-3_7zbMath1202.68274OpenAlexW1576394469MaRDI QIDQ5302044
Publication date: 20 January 2009
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://depositonce.tu-berlin.de/handle/11303/15645
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (7)
Complexity of the maximum leaf spanning tree problem on planar and regular graphs ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Max-leaves spanning tree is APX-hard for cubic graphs ⋮ An exact exponential-time algorithm for the directed maximum leaf spanning tree problem ⋮ A new algorithm for finding trees with many leaves ⋮ Spanning trees: A survey ⋮ Connected Domination
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A greedy approximation for minimum connected dominating sets
- Spanning trees in graphs of minimum degree 4 or 5
- Approximation algorithms for connected dominating sets
- On the approximability of some Maximum Spanning Tree Problems
- 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
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- Solving Connected Dominating Set Faster Than 2 n
- 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
This page was built for publication: A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
