An O(m + n log n) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs

ISSN： 0196-6774

Source： Journal of Algorithms, Vol.25, Iss.2, 1997-11, pp. : 336-358

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

We present an algorithm to compute, in O(m + n log n) time, a maximum clique in circular-arc graphs (with n vertices and m edges) provided a circular-arc model of the graph is given. If the circular-arc endpoints are given in sorted order, the time complexity is O(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 was O(m log log n + n log n), using an algorithm that solved an independent subproblem for each of the n circular arcs. By using the radial-sweep technique, we need not solve each of these subproblems independently; thus we eliminate the log log n factor from the running time of earlier algorithms. For vertex-weighted circular-arc graphs, it is possible to use our approach to obtain an O(m log log n + n log n) algorithm for finding a maximum-weight clique-which matches the best known algorithm. Copyright 1997 Academic Press.