کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141457 | 1489504 | 2013 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Sparse regular induced subgraphs in 2P32P3-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We call graphs of a fixed degree kksparse regular graphs and their complements dense regular graphs . Recently, it was conjectured that finding a maximum regular induced subgraph HH in a 2P32P3-free graph can be solved in polynomial time if and only if HH is sparse. In the present paper, we prove the “sparse” part of this conjecture, i.e., we show that for each fixed kk, the problem of finding a maximum kk-regular induced subgraph in a 2P32P3-free graph can be solved in polynomial time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 10, Issue 4, November 2013, Pages 304–309
Journal: Discrete Optimization - Volume 10, Issue 4, November 2013, Pages 304–309
نویسندگان
Vadim V. Lozin, Raffaele Mosca, Christopher Purcell,