کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429806 | 687682 | 2006 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Polynomial time recognition of unit circular-arc graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We present an efficient algorithm for recognizing unit circular-arc (UCA) graphs, based on a characterization theorem for UCA graphs proved by Tucker in the seventies. Given a proper circular-arc (PCA) graph G, the algorithm starts from a PCA model for G, removes all its circle-covering pairs of arcs and determines whether G is a UCA graph. We also give an O(N) time bound for Tucker's 3/2-approximation algorithm for coloring circular-arc graphs with N vertices, when a circular-arc model is given.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Algorithms - Volume 58, Issue 1, January 2006, Pages 67-78
Journal: Journal of Algorithms - Volume 58, Issue 1, January 2006, Pages 67-78