Complexities of some interesting problems on spanning trees

DOI10.1016/j.ipl.2004.12.016zbMath1182.68090OpenAlexW2059123237MaRDI QIDQ1041729

Mohammad Kaykobad, M. Sohel Rahman

Publication date: 4 December 2009

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

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

zbMATH Keywords

computational complexitycombinatorial problemsNP-completenessgraphsdecision problemspanning trees

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Scatter search for the minimum leaf spanning tree problem ⋮ Spanning Trees with Many Leaves in Regular Bipartite Graphs ⋮ Spanning trees: A survey ⋮ Variations of the maximum leaf spanning tree problem for bipartite graphs

Cites Work

• Constructing full spanning trees for cubic graphs
• Self-stabilizing systems in spite of distributed control
• On Representatives of Subsets
• Unnamed Item

This page was built for publication: Complexities of some interesting problems on spanning trees