@article(KeiSch92, author= "J. Mark Keil and Doug Schaefer", title= "An optimal algorithm for finding dominating cycles in circular-arc graphs", journal= "Discrete Applied Mathematics", annote= "An $O(n \log n)$ algorithm for finding a minimum cardinality dominating cycle in an interval graph and in a circular-arc grpah. It proves that under the algebraic computation tree computation model, $\Omega(n\log n)$ time is required to determine if a dominating cycle exists.", vol= 36, year= 1992, pages= "25-34") @article(GupLeeLeu82, author= "U. I. Gupta and D. T. Lee and J. Y. T. Leung", title= "Efficient algorithms for interval graphs and circular-arc graphs", journal= "Networks", annote= "An $O(n log n)$ algorithm for finding a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique in an interval graph given in the form of a family of intervals. It runs in $O(n)$ if the endpoints of the intervals are sorted. $O(n ^ 2)$ to find a maximum independent set and a minimum covering by disjoint completely connected sets or cliques in a circular-arc graph.", vol= 12, year= 1982, pages= "459-467") @article(HsuTsa91, author= "Wen-Lian Hsu and Kuo-Hui Tsai", title= "Linear time algorithms on circular-arc graphs", journal= "Information Processing Letters", annote= "An $O(n)$ algorithm sloves the maximum independent set, the minimum clique cover and the minimum dominating set problems simultaneously(unweighted version).", vol= 40, year= 1991, pages= "123-129") @article(BerMor90, author= "Alan A. Bertossi and Sabrina Moretti", title= "Parallel Algorithms on Circular-arc Graphs", journal= "Information Processing Letters", annote= "$O(log^2 n)$ parallel algorithm for finding a maximum weighted clique with $O(n\sp 4 /\log n )$ processors, a maximum weighted independent set, a minimum weighted dominating set and a minimum weighted total dominating set of a circular-arc graph by using $O(n\sp 3 /\log n)$ processors and a a shared memory model(SMM) of parallel computers. $O(n ^ 3)$ sequential algorithm for the minimum weighted dominating set and minimum weighted total dominating set problems.", vol= 33, year= 1990, pages= "275-281") @article(LeeSarWu90, author= "D. T. Lee and M. Sarrafzadeh and Y. F. Wu", title= "Minimum Cuts for Circular-arc Graphs", journal= "SIAM Journal on Computing", annote= "An $O(n log n)$ algorithm for finding a minimum cut of n arcs on a unit circle. Linear time if the endpoints of the arcs are sorted. Linear time to solve the maximum independent set of {\it n} arcs too under this condition.", vol= 19, year= 1990, pages= "1041-1050") @article(Tuc74, author= "Alan Tucker", title= "Structure Theorems for Some Circular-arc Graphs", journal= "Discrete Mathematics", annote= "This paper presents structure theorems for proper circular-arc graphs and for unit circular-arc grpahs", vol= 7, year= 1974, pages= "167-195") @article(Tuc75, author= "Alan Tucker", title= "Coloring a family of circular arcs", journal= "SIAM Journal on Applied Mathematics", annote= "The strong perfect graph conjecture is valid for circular-arc graphs. The problem of determining whether a family of arcs can be k-colored is converted into a multicommodity flow problem.", vol= 29, year= 1975, pages= "") @article(Tuc80, author= "Alan Tucker", title= "An Efficient Test for Circular-arc Graphs", journal= "SIAM Journal on Computing", annote= "An $O(n ^ 3)$ algorithm for testing if a {\it n}-vertex graph is a circular-arc graph.", vol= 9, year= 1980, pages= "1-24") @article(ShiCheHsu92, author= "Wei-Kuan Shih and T. C. Chern and Wen-Lian Hsu", title= "An $O(n^2 log n)$ algorithm for the Hamiltonian cycle problem on circular-arc graphs", journal= "SIAM Journal on Computing", annote= "An $O(n\sp 2 log n)$ algorithm for the Hamiltonian cycle problem in a given circular-arc graph.", vol= 21, year= 1992, pages= "1026-1046") @inproceedings(EscSpi93, author= "Elaine M. Eschen and Jeremy P. Spinrad", title= "An $O(n\sp 2)$ algorithm for circular-arc graph recognition", booktitle= "Collection: Proceedings of the Fourth Annual ACM-SIAM symposium on discrete algorithms(Austin, TX, 1993)", year= 1993, pages= "128-137", publisher= "ACM, New York", annote= "An $O(n\sp 2)$ algorithm for recognizing circular-arc graph. It also gets an $O(n\sp 2)$ time isomorphism test for circular-arc graphs.", note= "") @article(Asa93, author= "Takao Asano", title= "Dynamic programming on intervals", journal= "International Journal of Computational Geometry and Applications", annote= "An $O(m\log n)$ algorithm for partitioning a graph. Also an $O(n\log n)$ algorithm for finding a minimum weigh dominating set of an interval graph and an $O(m\log n)$ algorithm for finding a maximum weight clique of a circular-arc graph are given.", vol= 3, year= 1993, pages= "323-330") @article(KasMas91, author= "Toshinobu Kashiwabara and Sumio Masuda", title= "Polynomial time algorithms on circular-arc overlap graphs", journal= "Networks", annote= "An $O(n\sp 2)$ algorithm for finding a maximum independent set and an $O(n\sp 5)$ algorithm for finding a maximum clique in a circular-arc overlap graph with $n$ arcs.", vol= 21, year= 1991, pages= "195-203") @article(MasNak88, author= "Sumio Masuda and Kazuo Nakajima", title= "An optimal algorithm for finding a maximum independent set of a circular-arc graph", journal= "SIAM Journal on Computing", annote= "An $O(n \log n)$ algorithm for finding a maximum independent set of a circular-arc graph in $O(n)$ space is provided. If the endpoints of the arcs are sorted, it will run in $O(n)$ time.", vol= 17, year= 1988, pages= "41-52") @article(RaoPan89, author= "A. Srinivasa Rao and Rangan C. Pandu", title= "Optimal parallel algorithms on circular-arc graphs", journal= "Information Processing Letters", annote= "To finding an (unweighted) maximum independent set, a minimum clique cover and a minimum dominating set on circular-arc grphs, a parallel algorithms running in $O(\log n)$ time with $O(n/\log n)$ processors using the EREW PRAM model is presented.", vol= 33, year= 1989, pages= "147-156") @article(KasMasNakFuj92, author= "Toshinobu Kashiwabara and Sumio Masuda and Kazuo Nakajima and Toshio Fujisawa", title= "Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph", journal= "Journal of Algorithms", annote= "An $O(n\sp {2.5}\, +$(output size)) algorithm for generating all maximum independent sets of a bipartite graph is given. It also presents an $O(n\sp {3.5}\,+$ (output size)) algorithm that generates all maximum cliques of a circular-arc graph.", vol= 13, year= 1992, pages= "161-174") @article(Kim90, author= "Sung Kwon Kim", title= "A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle", journal= "Information Precessing Letters", annote= "To find a maximum clique of a circular-arc graph, a parallel algorithm runs in $O(\log\sp 2n)$ time using $O(n\sp 3/\log n)$ processors in the CREW PRAM model is presented.", vol= 34, year= 1990, pages= "235-241") @article(ShiHsu89, author= "Wei Kuan Shih and Wen Lian Hsu", title= "An $O(n\log n+m\log\log n)$ maximum weight clique algorithm for circular-arc graphs", journal= "Information Precessing Letters", annote= "An $O(n\log n+m\log\log n)$ algorithm is given to solve the weighted case of the maximum weight clique problem.", vol= 31, year= 1989, pages= "129-134") @article(ApoHam89, author= "Alberto Apostolico and Susanne E. Hambrusch", title= "Finding maximum cliques on circular-arc graphs in $O(n\sp 2 \log\log n)$ ", journal= "Information Precessing Letters", annote= "An $O(n\sp 2 \log\log n)$ algorithm is given to solve the unweighted case of the maximum-sized clique problem.", vol= 26, year= 1987, pages= "209-215") @article(Gav74, author= "F. Gavril", title= "Algorithms on circular-arc graphs", journal= "Networks", annote= "An $O(n\sp 4)$ algorithm for finding a maximum independent set. An $O(n\sp 5)$ algorithm for finding a minimum covering by cliques, and an $O(n\sp 3)$ algorithm for finding a maximum clique of a circular-arc graph.", vol= 4, year= 1974, pages= "357-369") @article(Tuc71, author= "Alan Tucker", title= "Matrix Characterizations of Circular-arc Graphs", journal= "Pacific Journal of Mathematics", annote= "Circular-arc graphs' adjacency matrix has the quasi-circular 1's property", vol= 39, year= 1971, pages= "535-545") @article(Kle69, author= "Victor Klee", title= "What are the intersection graphs of arcs in a circle?", journal= "American Mathematics Monthly", annote= "Poses the circular-arc characterization and recognition problems", vol= 76, year= 1969, pages= "810-813") @Inproceedings(Tuc76, author= "Alan Tucker", title= "Circular arc graphs: new uses and a new algorithm", booktitle= "Theory and Applications of Graphs Proceedings, Michigan 1976", annote= "An $O(n ^ 4)$ algorithm for testing if a {\it n}-vertex graph is a circular-arc graph.", year= 1976) @unpublished(ShiHsu95, author= "Wei-Kuan Shih and Wen-Lian Hsu", title= "An Approximation Algorithm for Coloring Circular-arc Graphs", note= "between 1987 and 1993", annote= "An coloring algorithm which uses no more than $\alpha$ $\cdot$ q colors, where $\alpha$ = 5/3 and q is the size of a maximum clique in F.") @incollection(AtaCheLee93A, author= "Mikhail J. Atallah and Danny Z. Chen and D. T. Lee", title= "An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications", booktitle= "Collection: Algorithms--ESA '93", year= "1993", publisher= "Springer, Berlin", pages= "13-24") @incollection(AtaCheLee93B, author= "Mikhail J. Atallah and Danny Z. Chen and D. T. Lee", title= "Computing the all-paris longest chains in the plane.", booktitle= "Collection: Algorithms--ESA '93", year= "1993", publisher= "Springer, Berlin", pages= "1-13") @article(LiaRhe93, author= "Y. Daniel Liang and Chongkye Rhee", title= "Finding a maximum matching in a circular-arc graph", journal= "Information Processing Letters", annote= "An $O(n\log n)$ algorithm for finding a maximum matching in a circular-arc graph.", vol= 45, year= "1993", pages= "185-190") @article(AriPan91, author= "Srinivasa R. Arikati and C. Pandu Rangan", title= "Efficient reduction for path problems on circular-arc graphs", journal= "BIT. Computer Science Numberical Mathematics", annote= "An $O(n+m)$ algorithm for the parity path problem on proper circular-arc graphs, and $O(n\cdot m)$ algorithm for the parity path problem on circular-arc graphs.", vol= 31, year= "1991", pages= "182-193") @article(SenDasWes89, author= "M. Sen and S. Das and Douglas B. West", title= "Circular-arc digraphs: a characterization", journal= "Journal of Graph Theory", annote= "It gives matrix characterization of interval digraphs and circular-arc digraphs.", vol= 13, year= "1989", pages= "581-592") @article(Spi88, author= "Jeremy Spinrad", title= "Circular-arc graphs with clique cover number two", journal= "Journal of Combinatorial Theory Series B", annote= "It shows that problems on circular-arc graphs can be partitioned into two cliques are reducible to problems on two dimensional partial orders. It simplify the recognition algorithm by Tuc80 and the algorithm for determining whether two circular-arc graphs are isomorphic.", vol= 44, year= "1988", pages= "300-306") @incollection(SriPan89, author= "A. Rao Srinivasa and Rangan C. Pandu", title= "Linear algorithms for parity path and two path problems on circular-arc graph", booktitle= "Collection: Algorithms and data structures, (ottawa, ON, 1989)", year= "1989", publisher= "Springer, Berlin", pages= "267-290") @article(Dam93, author= "Peter Damaschke", title= "Paths in interval graphs and circular arc graphs", journal= "Discrete Mathematics", annote= "An $O(n\sp 5)$ algorithm for finding Hamiltonian paths in circular arc graphs.", vol= 112, year= "1993", pages= "49-64") @article(Ham88, author= "Golumbic Hammer", title= "Stability in circular-arc graphs", journal= "Journal on Algorithm", annote= "", vol= 9, year= "1988", pages= "314-320") @article(HsuSpi95, author= "Wen-Lian Hsu and Jeremy P. Spinrad", title= "Independent Sets in Circular-Arc Graphs", journal= "Journal of Algorithms", annote= " When the circular-arc graph is given as a set of adjacency lists, the independent set problem can be solved in $O(n + m)$ time.", vol= 19, year= "1995", pages= "145-160")