Premium
Finding maximum cliques in circle graphs
Author(s) -
Rotem D.,
Urrutia J.
Publication year - 1981
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.3230110305
Subject(s) - combinatorics , mathematics , circle graph , vertex (graph theory) , chord (peer to peer) , graph , clique graph , discrete mathematics , algorithm , computer science , graph power , line graph , distributed computing
A circle diagram consists of a circle C and a set of n chords. This diagram defines a graph with n vertices where each vertex corresponds to a chord, and two vertices are adjacent if their corresponding chords intersect in C . A graph G is called a circle graph if it is defined by some circle diagram. An algorithm which requires O(n 2 ) steps to generate one maximum clique is presented. The algorithm can also be used to generate all maximum cliques where the number of steps need to generate each additional maximum clique is linear in its size. This compares favourably with Gavril's algorithm [4] which works in O(n 3 ) steps.