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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
PublisherAssociation for Computing Machinery
Pages188-194
Number of pages7
ISBN (Print)0897913760
StatePublished - Mar 1 1991
Externally publishedYes
Event2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 - San Francisco, United States
Duration: Jan 28 1991Jan 30 1991

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
Country/TerritoryUnited States
CitySan Francisco
Period1/28/911/30/91

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'A sublinear-time randomized parallel algorithm for the maximum clique problem in perfect graphs'. Together they form a unique fingerprint.

Cite this