• DocumentCode
    2891496
  • Title

    Approximating clique is almost NP-complete

  • Author

    Feige, U. ; Goldwasser, S. ; Lovász, L. ; Safra, S. ; Szegedy, M.

  • Author_Institution
    Princeton Univ., NJ, USA
  • fYear
    1991
  • fDate
    1-4 Oct 1991
  • Firstpage
    2
  • Lastpage
    12
  • Abstract
    The computational complexity of approximating ω(G), the size of the largest clique in a graph G, within a given factor is considered. It is shown that if certain approximation procedures exist, then EXPTIME=NEXPTIME and NP=P
  • Keywords
    computational complexity; almost NP-complete; approximating clique; approximation procedures; computational complexity; graph; Approximation algorithms; Computational complexity; Data mining; Polynomials; Protocols; Testing; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
  • Conference_Location
    San Juan
  • Print_ISBN
    0-8186-2445-0
  • Type

    conf

  • DOI
    10.1109/SFCS.1991.185341
  • Filename
    185341
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2891496