Show simple item record

Efficient Algorithms for Finding Maximum Cliques of an Overlap Graph.

dc.contributor.authorMasuda, Sumioen_US
dc.contributor.authorNakajima, K.en_US
dc.contributor.authorKashiwabara, Toshinobuen_US
dc.contributor.authorFujisawa, Toshioen_US
dc.description.abstractLet F = {I_1, I_2, ..., I_n} be a finite family of closed intervals on the real line. For two distinct intervals I_j and I_k in F, we say that I_j and I_k overlap with each other if they interact with each other 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 two intervals in F overlap with each other. In this paper, we present two efficient algorithms for finding maximum cliques of an overlap graph when the graph is given in the form of a family of intervals. The first algorithm finds a maximum clique in O time, where n , m are the numbers of vertices , edges, respectively, WEIRD GREEK LETTER is the size of a maximum clique of the graph. The second algorithm generates all maximum cliques of the graph in O time, where WEIRD GREEK LETTER is the total sum of the sizes of the maximum cliques.en_US
dc.format.extent889505 bytes
dc.relation.ispartofseriesISR; TR 1986-58en_US
dc.titleEfficient Algorithms for Finding Maximum Cliques of an Overlap Graph.en_US
dc.typeTechnical Reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record