Complexity of spanning tree problems with leaf-dependent objectives

DOI10.1002/(SICI)1097-0037(199605)27:3%3C175::AID-NET2%3E3.0.CO;2-FMaRDI QIDQ4887748zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

optimal spanning tree

Mathematics Subject Classification ID

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

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

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)