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

DOI10.1016/J.TCS.2016.02.011zbMATH Open1336.68106OpenAlexW2275786105MaRDI QIDQ264582FDOQ264582

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

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

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)

Cites Work

• Title not available (Why is that?)
• 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
• Max-leaves spanning tree is APX-hard for cubic graphs
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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

Cited In (10)

• Title not available (Why is that?)
• 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
• Complexity of spanning tree problems with leaf-dependent objectives

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)