کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
417979 681597 2016 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Algorithmic aspects of switch cographs
ترجمه فارسی عنوان
جنبه های الگوریتمی نمودارهای مشترک سوئیچ
کلمات کلیدی
الگوریتم های گراف و تجزیه؛ 2-ساختار؛ تجزیه مدولار؛ تجزیه مدولار انفجار؛ نمودارهای مشترک سوئیچ
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

This paper introduces the notion of involution module, the first generalization of the modular decomposition of 2-structures which has a unique linear-sized decomposition tree. We derive an O(n2)O(n2) decomposition algorithm and we take advantage of the involution modular decomposition tree to obtain several algorithmic results. It is well-known that cographs (or equivalently P4P4-free graphs) are the graphs that are totally decomposable w.r.t modular decomposition. In a similar way, we introduce the class of switch cographs, as the class of graphs that are totally decomposable w.r.t involution modular decomposition. This class generalizes the class of cographs and appears to be exactly the class of (Bull, Gem, Co-Gem, C5C5)-free graphs. We use our new decomposition tool to design three practical algorithms for the maximum cut, vertex cover and vertex separator problems. The complexity of these problems was still unknown for this class of graphs. This paper also improves the complexity of the maximum clique, the maximum independent set, the chromatic number and the maximum clique cover problems by giving efficient algorithms, thanks to the decomposition tree. Eventually, we show that this class of graphs has clique-width at most 4 and that a clique-width expression can be computed in linear time.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 200, 19 February 2016, Pages 23–42
نویسندگان
, , ,