کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331403 | 686688 | 2005 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexities of some interesting problems on spanning trees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 94, Issue 2, 30 April 2005, Pages 93-97
Journal: Information Processing Letters - Volume 94, Issue 2, 30 April 2005, Pages 93-97
نویسندگان
M. Sohel Rahman, M. Kaykobad,