کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950882 | 1441038 | 2017 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Decycling with a matching
ترجمه فارسی عنوان
اتمام با تطبیق
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
دور زدن تطابق، بازخورد مجموعه رشته، الگوریتم های گراف،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
As a natural variant of the many decycling notions studied in graphs, we consider the problem to decide whether a given graph G has a matching M such that GâM is a forest. We establish NP-completeness of this problem for 2-connected planar subcubic graphs, and describe polynomial time algorithms that also determine such a matching if it exists for graphs that are claw- and paw-free, P5-free, chordal, and C4-free distance hereditary.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 124, August 2017, Pages 26-29
Journal: Information Processing Letters - Volume 124, August 2017, Pages 26-29
نویسندگان
Carlos V.G.C. Lima, Dieter Rautenbach, Uéverton S. Souza, Jayme L. Szwarcfiter,