کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423891 | 1632593 | 2011 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Partitioning Chordal Graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Matrix partition problems generalize graph colouring and homomorphism problems and occur frequently in the study of perfect graphs. It is difficult to decide, even for a small matrix M, whether the M-partition problem is polynomial time solvable or NP-complete (or possibly neither), and whether M-partitionable graphs can be characterized by a finite set of forbidden induced subgraphs (or perhaps some other first order condition). We discuss these problems for the class of chordal graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 325-330
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 325-330
نویسندگان
Tomás Feder, Pavol Hell, Shekoofeh Nekooei Rizi,