کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420766 | 683977 | 2008 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Solving some NP-complete problems using split decomposition
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Solving some NP-complete problems using split decomposition Solving some NP-complete problems using split decomposition](/preview/png/420766.png)
چکیده انگلیسی
We show how to use the split decomposition to solve some NP-hard optimization problems on graphs. We give algorithms for clique problem and domination-type problems. Our main result is an algorithm to compute a coloration of a graph using its split decomposition. Finally we show that the clique-width of a graph is bounded if and only if the clique-width of each representative graph in its split decomposition is bounded.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 14, 28 July 2008, Pages 2768–2780
Journal: Discrete Applied Mathematics - Volume 156, Issue 14, 28 July 2008, Pages 2768–2780
نویسندگان
Michaël Rao,