Complexity of spanning tree problems with leaf-dependent objectives

DOI10.1002/(SICI)1097-0037(199605)27:3%3C175::AID-NET2%3E3.0.CO;2-FzbMATH Open0851.90123OpenAlexW1983365347MaRDI QIDQ4887748FDOQ4887748

Authors: Mauro Dell'Amico, Martine Labbé, Francesco Maffioli 

Publication date: 5 August 1996

Full work available at URL: https://doi.org/10.1002/(sici)1097-0037(199605)27:3%3C175::aid-net2%3E3.0.co;2-f

Recommendations

• Complexity of the maximum leaf spanning tree problem on planar and regular graphs
• Spanning trees with constraints on the leaf degree
• The maximum-leaf spanning tree problem: Formulations and facets
• Approximation algorithms for the maximum leaf spanning tree problem on acyclic digraphs
• On spanning tree problems with multiple objectives
• An approximation algorithm for the maximum leaf spanning arborescence problem
• The complexity of the locally connected spanning tree problem
• Complexities of some interesting problems on spanning trees
• NP-completeness and degree restricted spanning trees
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time

zbMATH Keywords

optimal spanning tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Cited In (6)

• Complexity of the maximum leaf spanning tree problem on planar and regular graphs
• Memory-efficient enumeration of constrained spanning trees
• The complexity of spanning tree problems involving graphical indices
• Complexity of independency and cliquy trees
• Relations, models and a memetic approach for three degree-dependent spanning tree problems
• Complexities of some interesting problems on spanning trees

This page was built for publication: Complexity of spanning tree problems with leaf-dependent objectives

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