TY - GEN

T1 - A sublinear-time randomized parallel algorithm for the maximum clique problem in perfect graphs

AU - Alizadeh, Farid

N1 - Funding Information:
In this work, we will be studying algorithms for computation of maximum cliques and maximum independent sets in perfect graphs. A graph G = (V, E) is perfect when, for all of its induced subgraphs G\, the size of the maximum clique, w(G’), is equal to the size of the minimum vertex coloring x(G’). The celebrated perfect graph theorem of Lovasz [12] indicates that the complements of perfect graphs are also perfect; in other words, for all induced subgraphs G’ of G, the size of the largest independent set, cr(G’), is equal to the size of the minimum clique cover, p(G’). Grotschel, Lovasz and Schrijver have shown that for perfect graphs one can compute the largest clique and the largest independent set in polynomial time; see [6], [7], [8], and in particular, their elaborate book [9]. Their idea is based on computing an invariant known as the Lovasz number of graphs c9(G). Lovasz has shown that for all graphs u(G) < O(G) < x(G). As will be seen in the next section, 6(G) is defined as the minimum of some convex function derived from the graph. Grotschel, Lovasz and Schrijver use the ellipsoid method for convex pr~ gramming to establish polynomial time computability of O(G). For perfect graphs, since u(G) = (?(G) = x(G), it *This work was supported in part by the Air Force Office of Scientific Research grant AFOSR-87-0127, the National Science Foundation grant DCR-8420935 and the Minnesota Supercomputer Institute. t Computer Science Department, University of Minnesota, Minneapolis, Mn, 55455; e-mail: alizadeh@cs.umn .edu.
Publisher Copyright:
© 1991 Association for Computing Machinery. All rights reserved.

PY - 1991/3/1

Y1 - 1991/3/1

N2 - We will show that Lovasz number of graphs may be computed using interior-point methods. This technique will require O(√|V|) iterations, each consisting of matrix operations which have polylog parallel time complexity. In case of perfect graphs Lovasz number equals the size of maximum clique in the graph and thus may be obtained in sublinear parallel time. By using the isolating lemma, we get a Las Vegas randomized parallel algorithm for constructing the maximum clique in perfect graphs.

AB - We will show that Lovasz number of graphs may be computed using interior-point methods. This technique will require O(√|V|) iterations, each consisting of matrix operations which have polylog parallel time complexity. In case of perfect graphs Lovasz number equals the size of maximum clique in the graph and thus may be obtained in sublinear parallel time. By using the isolating lemma, we get a Las Vegas randomized parallel algorithm for constructing the maximum clique in perfect graphs.

UR - http://www.scopus.com/inward/record.url?scp=14644429133&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=14644429133&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:14644429133

SN - 0897913760

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 188

EP - 194

BT - Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991

PB - Association for Computing Machinery

T2 - 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991

Y2 - 28 January 1991 through 30 January 1991

ER -