کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872475 | 681651 | 2014 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Algorithms for unipolar and generalized split graphs
ترجمه فارسی عنوان
الگوریتم برای نمودارهای تقسیم یکپارچه و عمومی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تقسیم نمودار، نمودار تقسیم کلاسیک، گراف یکپارچه، نمودار تقسیم بندی عمومی، حداقل مثلث، کد کامل، مجموعه غلط کارآمد،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 195-201
نویسندگان
Elaine M. Eschen, Xiaoqiang Wang,