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.contributor.department | ISR | 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.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.identifier.uri | http://hdl.handle.net/1903/4483 | |
| 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 |
Files
Original bundle
1 - 1 of 1