کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419235 | 683758 | 2016 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Clique-width of path powers
ترجمه فارسی عنوان
عرض دسته قدرت مسیر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
عرض دسته ؛ نمودار فاصله مناسب؛ محاسبات خطی؛ خصوصیات زیرگرافی ناشی از ممنوعیت
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We describe the clique-width of path powers by an exact formula, depending only on the number of vertices and the clique number. As a consequence, the clique-width of path powers can be computed in linear time. Path powers are a graph class of unbounded clique-width. Prior to our result, square grids constituted the only known graph class of unbounded clique-width with a similar result. We also show that clique-width and linear clique-width coincide on path powers.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 205, 31 May 2016, Pages 62–72
Journal: Discrete Applied Mathematics - Volume 205, 31 May 2016, Pages 62–72
نویسندگان
Pinar Heggernes, Daniel Meister, Charis Papadopoulos, Udi Rotics,