کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419851 | 683868 | 2011 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the forbidden induced subgraph sandwich problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the forbidden induced subgraph sandwich problem On the forbidden induced subgraph sandwich problem](/preview/png/419851.png)
چکیده انگلیسی
We consider the sandwich problem, a generalization of the recognition problem introduced by Golumbic et al. (1995) [15], with respect to classes of graphs defined by excluding induced subgraphs. We prove that the sandwich problem corresponding to excluding a chordless cycle of fixed length kk is NP-complete. We prove that the sandwich problem corresponding to excluding Kr∖eKr∖e for fixed rr is polynomial. We prove that the sandwich problem corresponding to 3PC(⋅,⋅)3PC(⋅,⋅)-free graphs is NP-complete. These complexity results are related to the classification of a long-standing open problem: the sandwich problem corresponding to perfect graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 16, 28 September 2011, Pages 1717–1725
Journal: Discrete Applied Mathematics - Volume 159, Issue 16, 28 September 2011, Pages 1717–1725
نویسندگان
Simone Dantas, Celina M.H. de Figueiredo, Murilo V.G. da Silva, Rafael B. Teixeira,