Premium
Algorithms on circular‐arc graphs
Author(s) -
Gavril F.
Publication year - 1974
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230040407
Subject(s) - combinatorics , clique graph , mathematics , circle graph , intersection graph , split graph , vertex (graph theory) , arc (geometry) , discrete mathematics , block graph , graph , independent set , algorithm , line graph , 1 planar graph , graph power , geometry
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.