کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333005 | 688167 | 2005 | 34 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results](/preview/png/10333005.png)
چکیده انگلیسی
A very close relationship between the compaction, retraction, and constraint satisfaction problems has been established earlier providing evidence that it is likely to be difficult to give a complete computational complexity classification of the compaction and retraction problems for reflexive or bipartite graphs. In this paper, we give a complete computational complexity classification of the compaction and retraction problems for all graphs (including partially reflexive graphs) with four or fewer vertices. The complexity classification of both the compaction and retraction problems is found to be the same for each of these graphs. This relates to a long-standing open problem concerning the equivalence of the compaction and retraction problems. The study of the compaction and retraction problems for graphs with at most four vertices has a special interest as it covers a popular open problem in relation to the general open problem. We also give complexity results for some general graphs. The compaction and retraction problems are special graph colouring problems, and can also be viewed as partition problems with certain properties. We describe some practical applications also.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 71, Issue 4, November 2005, Pages 406-439
Journal: Journal of Computer and System Sciences - Volume 71, Issue 4, November 2005, Pages 406-439
نویسندگان
Narayan Vikas,