Polynomial time recognition of unit circular-arc graphs

作     者：Durán, G Gravano, A McConnell, RM Spinrad, J Tucker, A 

作者机构：Univ Chile Fac Ciencias Fis & Matemat Dept Ingn Ind Santiago Chile Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Computac Buenos Aires DF Argentina Colorado State Univ Dept Comp Sci Ft Collins CO 80528 USA Vanderbilt Univ Dept Elect Engn & Comp Sci Nashville TN 37235 USA SUNY Stony Brook Dept Appl Math Stony Brook NY 11794 USA 

出 版 物：《JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC》 (算法杂志)

年 卷 期：2006年第58卷第1期

页      面：67-78页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：International Scientific Cooperation Program CONICyT/SETCIP Millennium Science Nucleus Fondo Nacional de Desarrollo Científico y Tecnológico, FONDECYT, (1030498) Secretaría de Ciencia y Técnica, Universidad de Buenos Aires, UBACyT, (X127) 

主　　题：circular-arc graphs graph algorithms polynomial recognition proper circular-arc graphs 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. (C) 2004 Elsevier Inc. All rights reserved.