A 3-approximation algorithm for the maximum leaf \(k\)-forest problem

DOI10.1016/j.endm.2017.10.035zbMath1383.05056OpenAlexW2765669060MaRDI QIDQ2413172

Orlando Lee, Mário César San Felice, M. F. Reis, Fábio Luiz Usberti

Publication date: 9 April 2018

Full work available at URL: https://doi.org/10.1016/j.endm.2017.10.035

zbMATH Keywords

approximation algorithmsmaximum leaf spanning tree\(k\)-forest

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Approximation algorithms (68W25)

Related Items

Leafy spanning \(k\)-forests

Cites Work

• Unnamed Item
• Unnamed Item
• A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
• Constructing full spanning trees for cubic graphs
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time