کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421431 | 684226 | 2007 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Recognizing and representing proper interval graphs in parallel using merging and sorting
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Recognizing and representing proper interval graphs in parallel using merging and sorting Recognizing and representing proper interval graphs in parallel using merging and sorting](/preview/png/421431.png)
چکیده انگلیسی
We present a parallel algorithm for recognizing and representing a proper interval graph in O(log2n) time with O(m+n)O(m+n) processors on the CREW PRAM, where m and n are the number of edges and vertices in the graph. The algorithm uses sorting to compute a weak linear ordering of the vertices, from which an interval representation is easily obtained. It is simple, uses no complex data structures, and extends ideas from an optimal sequential algorithm for recognizing and representing a proper interval graph [X. Deng, P. Hell, J. Huang, Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs, SIAM J. Comput. 25 (2) (1996) 390–403].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 155, Issue 4, 15 February 2007, Pages 442–456
Journal: Discrete Applied Mathematics - Volume 155, Issue 4, 15 February 2007, Pages 442–456
نویسندگان
Jørgen Bang-Jensen, Jing Huang, Louis Ibarra,