# Efficient Algorithms for Finding Maximum Cliques of an Overlap Graph.

 dc.contributor.author Masuda, Sumio en_US dc.contributor.author Nakajima, K. en_US dc.contributor.author Kashiwabara, Toshinobu en_US dc.contributor.author Fujisawa, Toshio en_US dc.date.accessioned 2007-05-23T09:35:44Z dc.date.available 2007-05-23T09:35:44Z dc.date.issued 1986 en_US dc.identifier.uri http://hdl.handle.net/1903/4483 dc.description.abstract Let 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.extent 889505 bytes dc.format.mimetype application/pdf dc.language.iso en_US en_US dc.relation.ispartofseries ISR; TR 1986-58 en_US dc.title Efficient Algorithms for Finding Maximum Cliques of an Overlap Graph. en_US dc.type Technical Report en_US dc.contributor.department ISR en_US
﻿