کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647081 1342327 2015 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Weighted well-covered claw-free graphs
ترجمه فارسی عنوان
نمودار های بدون نقص دارای وزن خوب
کلمات کلیدی
گراف کاملا تحت پوشش نمودار متعادل کننده نمودار بدون چنگال، مجموعه مستقل حداکثر، تطابق حداکثر،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A graph G is equimatchable if all its maximal matchings are of the same cardinality. Assume that a weight function w is defined on the edges of G. Then G is w-equimatchable if all its maximal matchings are of the same weight. For every graph G, the set of weight functions w such that G is w-equimatchable is a vector space. We present an O(m⋅n4+n5logn) algorithm, which receives an input graph G, and outputs the vector space of weight functions w such that G is w-equimatchable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 338, Issue 3, 6 March 2015, Pages 99-106
نویسندگان
, ,