Premium
Efficient algorithms for finding maximum cliques of an overlap graph
Author(s) -
Masuda Sumio,
Nakajima Kazuo,
Kashiwabara Toshinobu,
Fujisawa Toshio
Publication year - 1990
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.3230200203
Subject(s) - combinatorics , mathematics , graph , clique graph , clique , algorithm , discrete mathematics , line graph , graph power
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.