کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431038 | 688259 | 2011 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Parameterized complexity of even/odd subgraph problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We study the parameterized complexity of the problems of determining whether a graph contains a k-edge subgraph (k-vertex induced subgraph) that is a Π-graph for Π-graphs being one of the following four classes of graphs: Eulerian graphs, even graphs, odd graphs, and connected odd graphs. We also consider the parameterized complexity of their parametric dual problems.For these sixteen problems, we show that eight of them are fixed parameter tractable and four are W[1]-hard. Our main techniques are the color-coding method of Alon, Yuster and Zwick, and the random separation method of Cai, Chan and Chan.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 9, Issue 3, September 2011, Pages 231–240
Journal: Journal of Discrete Algorithms - Volume 9, Issue 3, September 2011, Pages 231–240
نویسندگان
Leizhen Cai, Boting Yang,