کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1710389 | 1012887 | 2007 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A faster parallel connectivity algorithm on cographs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
سایر رشته های مهندسی
مکانیک محاسباتی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A faster parallel connectivity algorithm on cographs A faster parallel connectivity algorithm on cographs](/preview/png/1710389.png)
چکیده انگلیسی
Cographs are a well-known class of graphs arising in a wide spectrum of practical applications. In this note, we show that the connected components of a cograph GG can be optimally found in O(logloglogΔ(G)) time using O((n+m)logloglogΔ(G)) processors on a common CRCW PRAM, or in O(logΔ(G)) time using O((n+m)logΔ(G)) processors on an EREW PRAM, where Δ(G) is the maximum degree of GG, and nn and mm respectively are the numbers of vertices and edges of GG. These are faster than the previously best known result on general graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics Letters - Volume 20, Issue 3, March 2007, Pages 341–344
Journal: Applied Mathematics Letters - Volume 20, Issue 3, March 2007, Pages 341–344
نویسندگان
Sun-Yuan Hsieh,