Concepedia

Maximum Clique Approximation

Maximum Clique Approximation is an approximation algorithm designed to find a maximal complete subgraph in an undirected graph, differing from exact clique algorithms by providing a computationally efficient solution with a guaranteed performance ratio relative to the optimal clique size.

108

Publications

9.4K

Citations

241

Authors

148

Institutions

Publications per year

2017–2026

18

Parents

Publications

108

New methods to color the vertices of a graph

Daniel Brélaz · Communications of the ACM · 1979 · 1.6K citations · Full text

, , +16

Proof verification and hardness of approximation problems

Sanjeev Arora, Carsten Lund, R. Motwani et al. · 1992 · 744 citations

, , +16

A fast algorithm for the maximum clique problem

Patric R. J. Östergård · Discrete Applied Mathematics · 2002 · 598 citations

, , +10

Interactive proofs and the hardness of approximating cliques

Uriel Feige, Shafi Goldwasser, László Lovász et al. · Journal of the ACM · 1996 · 524 citations · Full text

, , +16

An exact algorithm for the maximum clique problem

Randy Carraghan, Pãnos M. Pardalos · Operations Research Letters · 1990 · 518 citations

, , +10

1–5 of 108

Authors

241

  1. AJ
    Arun Jagota

    University of California, Santa Cruz, United States

    4 publications · 133 citations

    4

    h-index

  2. MS
    Márió Szegedy

    Rutgers, The State University of New Jersey, United States

    3 publications · 1.3K citations

    3

    h-index

  3. BB
    Binay Bhattacharya

    Simon Fraser University, Canada

    3 publications · 49 citations

    3

    h-index

  4. EB
    Egon Balas

    Carnegie Mellon University, United States

    3 publications · 393 citations

    3

    h-index

  5. SB
    Sergiy Butenko

    Texas A&M University, United States

    3 publications · 82 citations

    3

    h-index

1–5 of 241

Institutions

148

  1. AT&T (United States)

    Bedminster, United States

    4 h-index

    7 publications

    2.1K citations

  2. University of Haifa

    Haifa, Israel

    4 h-index

    5 publications

    116 citations

  3. Centre National de la Recherche Scientifique

    Paris, France

    4 h-index

    10 publications

    469 citations

  4. University of Maryland, College Park

    College Park, United States

    4 h-index

    6 publications

    145 citations

  5. Simon Fraser University

    Burnaby, Canada

    3 h-index

    7 publications

    102 citations

  6. Université Paris Cité

    Paris, France

    3 h-index

    5 publications

    407 citations

  7. University at Buffalo, State University of New York

    Buffalo, United States

    3 h-index

    3 publications

    63 citations

  8. Carnegie Mellon University

    Pittsburgh, United States

    3 h-index

    3 publications

    169 citations

1–8 of 148

Venues

  1. Information Processing Letters

    5 publications · 137 citations

    5

    h-index

  2. Algorithmica

    4 publications · 147 citations

    4

    h-index

  3. Discrete Applied Mathematics

    4 publications · 696 citations

    4

    h-index

  4. SIAM Journal on Computing

    4 publications · 449 citations

    4

    h-index

  5. Theoretical Computer Science

    4 publications · 182 citations

    4

    h-index

1–5