Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331403 | Information Processing Letters | 2005 | 5 Pages |
Abstract
This paper deals with the complexity issues of some new interesting spanning tree problems. Here we define some new spanning tree problems by imposing various constraints and restrictions on graph parameters and present relevant results. Also we introduce a new notion of “set version” of some decision problems having integer K<|V| as a parameter in the input instance, where we replace K by a set Xâ|V|. For example, the set version of Maximum Leaf Spanning Tree problem asks whether there exists a spanning tree in G that contains X as a subset of the leaf set. We raise the issue of whether the set versions of NP-complete problems are as hard as the original problems and prove that although in some cases the set versions are easier to solve, this is not necessarily true in general.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
M. Sohel Rahman, M. Kaykobad,