Complexity of the maximum leaf spanning tree problem on planar and regular graphs

DOI10.1016/j.tcs.2016.02.011zbMath1336.68106OpenAlexW2275786105MaRDI QIDQ264582

Alexander Reich

Publication date: 31 March 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.02.011

zbMATH Keywords

cubic graphplanar graphNP-hardnessAPX-hardnessmaximum leaf spanning tree

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Optimization of wireless sensor networks deployment with coverage and connectivity constraints ⋮ A method to calculate the number of spanning connected unicyclic(bicyclic) subgraphs in 2-separable networks ⋮ Connected domination in maximal outerplanar graphs ⋮ The complexity of spanning tree problems involving graphical indices ⋮ Invulnerability of planar two-tree networks ⋮ Connected Domination

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Max-leaves spanning tree is APX-hard for cubic graphs
• Construction of strongly connected dominating sets in asymmetric multihop wireless networks
• A short note on the approximability of the maximum leaves spanning tree problem
• The regenerator location problem
• Planar 3DM is NP-complete
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
• A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs

This page was built for publication: Complexity of the maximum leaf spanning tree problem on planar and regular graphs