Algorithms for a maximum clique and a maximum independent set of a circle graph | Zendy

Gavril F. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research