کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9655163 | 684032 | 2005 | 34 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Efficient parallel recognition of cographs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Efficient parallel recognition of cographs Efficient parallel recognition of cographs](/preview/png/9655163.png)
چکیده انگلیسی
In this paper, we establish structural properties for the class of complement reducible graphs or cographs, which enable us to describe efficient parallel algorithms for recognizing cographs and for constructing the cotree of a graph if it is a cograph; if the input graph is not a cograph, both algorithms return an induced P4. For a graph on n vertices and m edges, both our cograph recognition and cotree construction algorithms run in O(log2n) time and require O((n+m)/logn) processors on the EREW PRAM model of computation. Our algorithms are motivated by the work of Dahlhaus (Discrete Appl. Math. 57 (1995) 29-44) and take advantage of the optimal O(logn)-time computation of the co-connected components of a general graph (Theory Comput. Systems 37 (2004) 527-546) and of an optimal O(logn)-time parallel algorithm for computing the connected components of a cograph, which we present. Our results improve upon the previously known linear-processor parallel algorithms for the problems (Discrete Appl. Math. 57 (1995) 29-44; J. Algorithms 15 (1993) 284-313): we achieve a better time-processor product using a weaker model of computation and we provide a certificate (an induced P4) whenever our algorithms decide that the input graphs are not cographs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 150, Issues 1â3, 1 September 2005, Pages 182-215
Journal: Discrete Applied Mathematics - Volume 150, Issues 1â3, 1 September 2005, Pages 182-215
نویسندگان
Stavros D. Nikolopoulos, Leonidas Palios,