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

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