کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872227 | 681647 | 2014 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Square roots of minor closed graph classes
ترجمه فارسی عنوان
ریشه های مربع کلاس های گراف محدود است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
ریشه های مربع از نمودار، شعبه عرض، حکاکی عرض، جوانان گراف
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let G be a graph class. The square root of G contains all graphs whose squares belong in G. We prove that if G is non-trivial and minor closed, then all graphs in its square root have carving-width bounded by some constant depending only on G. As a consequence, every square root of such a graph class has a linear time recognition algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 168, 11 May 2014, Pages 34-39
Journal: Discrete Applied Mathematics - Volume 168, 11 May 2014, Pages 34-39
نویسندگان
Nestor V. Nestoridis, Dimitrios M. Thilikos,