Efficient algorithms for finding maximum cliques of an overlap graph

✍ Scribed by Sumio Masuda; Kazuo Nakajima; Toshinobu Kashiwabara; Toshio Fujisawa

• Publisher: John Wiley and Sons
• Year: 1990
• Tongue: English
• Weight: 728 KB
• Volume: 20
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230200203

✦ Synopsis

Let F = { I , , 12,. . . , Z,,} be a finite family of closed intervals on the real line. Two intervals 4 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. T h e first algorithm finds a maximum clique in O ( n . log n + Min{m, n . o}) time, where m is the number of edges and w is the size of a maximum clique, respectively, of the graph. The second algorithm generates all maximum cliques in O(n . log n + m + y) time, where y is the total sum of their sizes. *At time of study, was o n leave with. the Electrical Engineering Department and Systems Research Center at the University of Maryland. tNow on leave with the Electrical Engineering Department and Institute for Advanced Computer Studies at the University of Maryland. $Deceased on December 15, 1988.