کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6872227 681647 2014 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Square roots of minor closed graph classes
ترجمه فارسی عنوان
ریشه های مربع کلاس های گراف محدود است
کلمات کلیدی
ریشه های مربع از نمودار، شعبه عرض، حکاکی عرض، جوانان گراف
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, ,