Variations of the maximum leaf spanning tree problem for bipartite graphs

DOI10.1016/J.IPL.2005.10.011MaRDI QIDQ1045917zbMATH OpenOpenAlexFDO

Authors P. C. Li, Michel Toulouse

Publication date 18 December 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2005.10.011

zbMATH Keywords

computational complexityNP-completebipartite graphsmaximum leaf spanning trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• NP-completeness and degree restricted spanning trees
• Complexity of the maximum leaf spanning tree problem on planar and regular graphs
• Spanning Trees with Many Leaves in Regular Bipartite Graphs
• Degree-preserving spanning trees in small-degree graphs
• Minimum perfect bipartite matchings and spanning trees under categorization

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Complexities of some interesting problems on spanning trees
• Constructing full spanning trees for cubic graphs
• Hard tiling problems with simple tiles

Cited in

(7)

• The connected domination number of grids
• Spanning trees: A survey
• Minimum entropy orientations
• On the analysis of the \((1+1)\) evolutionary algorithm for the maximum leaf spanning tree problem
• Minimum perfect bipartite matchings and spanning trees under categorization
• Spanning Trees with Many Leaves in Regular Bipartite Graphs
• Complexities of some interesting problems on spanning trees

This page was built for publication: Variations of the maximum leaf spanning tree problem for bipartite graphs

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