Premium
Algorithms for a maximum clique and a maximum independent set of a circle graph
Author(s) -
Gavril F.
Publication year - 1973
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.3230030305
Subject(s) - combinatorics , circle graph , independent set , mathematics , split graph , block graph , clique graph , vertex (graph theory) , biconnected graph , chord (peer to peer) , chordal graph , discrete mathematics , graph , computer science , line graph , pathwidth , graph power , 1 planar graph , distributed computing
Consider a family of chords in a circle. A circle graph is obtained by representing each chord by a vertex, two vertices being connected by an edge when the corresponding chords intersect. In this paper, we describe efficient algorithms for finding a maximum clique and a maximum independent set of circle graphs. These algorithms require at most n 3 steps, where n is the number of vertices in the graph.