NP-completeness and degree restricted spanning trees
type: Item
instance of: scholarly article
title: NP-completeness and degree restricted spanning trees
zbMATH Open document ID: 0777.05043
DOI: 10.1016/0012-365X(92)90130-8
author: Robert James Douglas
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: The author proves among other results that the problem of deciding whether a given planar graph with maximum degree 3 has a spanning tree with node degrees 1 or 3 is NP-complete. The proof is based on a polynomial transformation from the Hamiltonian Path Variant Problem using a local replacement argument. As a corollary the author shows that it is NP-complete to decide if there is a spanning tree for such a graph with at least \(n/2+1\) leaves.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 94345
zbMATH Keywords: NP-completeness
zbMATH Keywords: planar graph
zbMATH Keywords: spanning tree
Wikidata QID: Q29036420
reviewed by: Patrick Jaillet
MaRDI profile type: Publication
cites work: Graphs with homeomorphically irreducible spanning trees
cites work: Q4198056
cites work: The Planar Hamiltonian Circuit Problem is NP-Complete
full work available at URL: 0012-365x(92)90130-8
OpenAlex ID: W2067078311
description: scientific article; zbMATH DE number 94345