Efficient algorithms for finding maximum cliques of an overlap graph

Let F = { I 1 , I 2 ,…, I n } be a finite family of closed intervals on the real line. Two intervals I j and I k in F are said to overlap each other if they intersect but neither one of them contains the other. A graph G = ( V , E ) is called an overlap graph for F if there is a one‐to‐one correspondence between V and F such that two vertices in V are adjacent to each other if and only if the corresponding intervals in F overlap each other. In this paper, we present two efficient algorithms for finding maximum cliques of an overlap graph when it is given in the form of a family of n intervals. The first algorithm finds a maximum clique in O ( n . log n + Min { m, n ‐ ω}) time, where m is the number of edges and ω is the size of a maximum clique, respectively, of the graph. The second algorithm generates all maximum cliques in O ( n ‐ log n + m + γ) time, where γ is the total sum of their sizes.