Variations of the maximum leaf spanning tree problem for bipartite graphs

DOI10.1016/j.ipl.2005.10.011zbMath1181.68176OpenAlexW2029112748MaRDI QIDQ1045917

(Ben) 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 complexitybipartite graphsNP-completemaximum 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)

Related Items (5)

The connected domination number of grids ⋮ On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem ⋮ Spanning Trees with Many Leaves in Regular Bipartite Graphs ⋮ Spanning trees: A survey ⋮ Minimum entropy orientations

Cites Work

• Unnamed Item
• Complexities of some interesting problems on spanning trees
• Constructing full spanning trees for cubic graphs
• Hard tiling problems with simple tiles

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