کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6872475 681651 2014 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Algorithms for unipolar and generalized split graphs
ترجمه فارسی عنوان
الگوریتم برای نمودارهای تقسیم یکپارچه و عمومی
کلمات کلیدی
تقسیم نمودار، نمودار تقسیم کلاسیک، گراف یکپارچه، نمودار تقسیم بندی عمومی، حداقل مثلث، کد کامل، مجموعه غلط کارآمد،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A graph G=(V,E) is a unipolar graph if there exists a partition V=V1∪V2 such that V1 is a clique and V2 induces the disjoint union of cliques. The complement-closed class of generalized split graphs contains those graphs G such that either Gor the complement of G is unipolar. Generalized split graphs are a large subclass of perfect graphs. In fact, it has been shown that almost all C5-free (and hence, almost all perfect graphs) are generalized split graphs. In this paper, we present a recognition algorithm for unipolar graphs that utilizes a minimal triangulation of the given graph, and produces a partition when one exists. Our algorithm has running time O(nm+nmF), where mF is the number of edges added in a minimal triangulation of the given graph. Generalized split graphs can be recognized via this algorithm in O(n3) time. We give algorithms on unipolar graphs for finding a maximum independent set and a minimum clique cover in O(n+m) time, and for finding a maximum clique and a minimum proper coloring in O(n2.5/logn) time, when a unipolar partition is given. These algorithms yield algorithms for the four optimization problems on generalized split graphs that have the same worst-case time bounds. We also report that the perfect code problem is NP-complete for chordal unipolar graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 195-201
نویسندگان
, ,