Algorithms on circular‐arc graphs | Zendy

Gavril F. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research