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

DOI10.1016/J.TCS.2016.02.011MaRDI QIDQ264582zbMATH OpenOpenAlexFDO

Authors 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

APX-hardnesscubic graphmaximum leaf spanning treeNP-hardnessplanar graph

Mathematics Subject Classification ID

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

Recommendations

• The maximum-leaf spanning tree problem: Formulations and facets
• Approximation algorithms for the maximum leaf spanning tree problem on acyclic digraphs
• Complexity of spanning tree problems with leaf-dependent objectives
• scientific article; zbMATH DE number 5777935
• An exact algorithm for the maximum leaf spanning tree problem
• An exact algorithm for the maximum leaf spanning tree problem
• An approximation algorithm for the maximum leaf spanning arborescence problem
• On the approximability of some maximum spanning tree problems
• On the approximability of some Maximum Spanning Tree Problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305098 (Why is no real title available?)
• scientific article; zbMATH DE number 1947432 (Why is no real title available?)
• 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
• A short note on the approximability of the maximum leaves spanning tree problem
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Construction of strongly connected dominating sets in asymmetric multihop wireless networks
• Max-leaves spanning tree is APX-hard for cubic graphs
• Planar 3DM is NP-complete
• The regenerator location problem

Cited in

(10)

• Complexity of spanning tree problems with leaf-dependent objectives
• scientific article; zbMATH DE number 5777935 (Why is no real title available?)
• Max-leaves spanning tree is APX-hard for cubic graphs
• Invulnerability of planar two-tree networks
• Connected domination in maximal outerplanar graphs
• Optimization of wireless sensor networks deployment with coverage and connectivity constraints
• The complexity of spanning tree problems involving graphical indices
• A method to calculate the number of spanning connected unicyclic(bicyclic) subgraphs in 2-separable networks
• Connected domination
• Variations of the maximum leaf spanning tree problem for bipartite graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q264582)