AnO(m + n log n) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs |
| |
Authors: | Binay K. Bhattacharya Damon Kaller |
| |
Affiliation: | School of Computing Science, Simon Fraser University, Burnaby, British Columbia, V5A 1S6, Canada |
| |
Abstract: | We present an algorithm to compute, inO(m + n log n) time, a maximum clique in circular-arc graphs (withnvertices andmedges) provided a circular-arc model of the graph is given. If the circular-arc endpoints are given in sorted order, the time complexity isO(m). The algorithm operates on the geometric structure of the circular arcs, radially sweeping their endpoints; it uses a very simple data structure consisting of doubly linked lists. Previously, the best time bound for this problem wasO(m log log n + n log n), using an algorithm that solved an independent subproblem for each of thencircular arcs. By using the radial-sweep technique, we need not solve each of these subproblems independently; thus we eliminate the log log nfactor from the running time of earlier algorithms. For vertex-weighted circular-arc graphs, it is possible to use our approach to obtain anO(m log log n + n log n) algorithm for finding a maximum-weight clique—which matches the best known algorithm. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|