EFFICIENT ALGORITHMS FOR FINDING MAXIMUM CLIQUES OF AN OVERLAP GRAPH

Let F = {I1, I2,…,In} be a finite family of closed intervals on the real line. Two intervals Ij and Ik 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. Copyright © 1990 Wiley Periodicals, Inc., A Wiley Company