کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10151234 685009 2018 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Characterizing graphs of maximum matching width at most 2
ترجمه فارسی عنوان
مشخص کردن گراف های حداکثر عرض تطبیق حداکثر 2
کلمات کلیدی
حداکثر عرض تطبیق مانعهای جزئی، توری،
ترجمه چکیده
حداکثر عرض تطبیق عرض پارامتر است که در یک تجزیه شاخه بر روی مجموعه رأس یک گراف تعریف شده است. اندازه تطبیق حداکثر در گراف دو طرفه به عنوان یک تابع برش استفاده می شود. در این مقاله، نمودارهای عرض حداکثر تطبیق را حداکثر 2 با استفاده از مجموعه انسداد جزئی مشخص می کنیم. همچنین، ما مقدار دقیق عرض حداکثر تطبیق شبکه را محاسبه می کنیم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
مشخص کردن گراف های حداکثر عرض تطبیق حداکثر 2
چکیده انگلیسی
The maximum matching width is a width-parameter that is defined on a branch-decomposition over the vertex set of a graph. The size of a maximum matching in the bipartite graph is used as a cut-function. In this paper, we characterize the graphs of maximum matching width at most 2 using the minor obstruction set. Also, we compute the exact value of the maximum matching width of a grid.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 248, 30 October 2018, Pages 102-113
نویسندگان
, , ,