Algorithms on circular‐arc graphs
- 1 January 1974
- Vol. 4 (4) , 357-369
- https://doi.org/10.1002/net.3230040407
Abstract
Consider a finite family of non‐empty sets. The intersection graph of this family is obtained by representing each set by a vertex, two vertices being connected by an edge if and only if the corresponding sets intersect. The intersection graph of a family of arcs on a circularly ordered set is called a circular‐arc graph. In this paper we give a characterization of the circular‐arc graph and we describe efficient algorithms for recognizing two subclasses. Also, we describe efficient algorithms for finding a maximum independent set, a minimum covering by cliques and a maximum clique of a circular‐arc graph.Keywords
This publication has 9 references indexed in Scilit:
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal GraphSIAM Journal on Computing, 1972
- Matrix characterizations of circular-arc graphsPacific Journal of Mathematics, 1971
- Triangulated graphs and the elimination processJournal of Mathematical Analysis and Applications, 1970
- What Are the Intersection Graphs of Arcs in a Circle?The American Mathematical Monthly, 1969
- What Are the Intersection Graphs of Arcs in a Circle?The American Mathematical Monthly, 1969
- Incidence matrices and interval graphsPacific Journal of Mathematics, 1965
- A Characterization of Comparability Graphs and of Interval GraphsCanadian Journal of Mathematics, 1964
- Representation of a finite graph by a set of intervals on the real lineFundamenta Mathematicae, 1962
- Minimizing the Number of States in Incompletely Specified Sequential Switching FunctionsIEEE Transactions on Electronic Computers, 1959