NP-completeness and degree restricted spanning trees

DOI10.1016/0012-365X(92)90130-8zbMath0777.05043OpenAlexW2067078311WikidataQ29036420 ScholiaQ29036420MaRDI QIDQ1199472

Robert James Douglas

Publication date: 16 January 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(92)90130-8

zbMATH Keywords

NP-completenessspanning treeplanar graph

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (11)

The VC-dimension of graphs with respect to \(k\)-connected subgraphs ⋮ Boundary classes for graph problems involving non-local properties ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ The \(k\)-leaf spanning tree problem admits a klam value of 39 ⋮ A win-win algorithm for the $(k+1)$-LST/$k$-pathwidth problem ⋮ Decomposing plane cubic graphs ⋮ On dominating sets whose induced subgraphs have a bounded diameter ⋮ Decomposing graphs into a spanning tree, an even graph, and a star forest ⋮ Decompositions of cubic traceable graphs ⋮ Complexity of independency and cliquy trees ⋮ Homeomorphically irreducible spanning trees in hexangulations of surfaces

Cites Work

• Unnamed Item
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Graphs with homeomorphically irreducible spanning trees

This page was built for publication: NP-completeness and degree restricted spanning trees