Concepedia

Maximum Independent Set Approximation

Maximum Independent Set Approximation is an approximation algorithm that belongs to the class of polynomial-time algorithms designed for NP-hard optimization problems, specifically distinguished by its objective to find an independent set of vertices in a graph with a size that is guaranteed to be within a certain approximation ratio of the maximum possible size.

263

Publications

14.8K

Citations

555

Authors

285

Institutions

Publications per year

2017–2026

54

Parents

Publications

263

Approximation algorithms for NP-complete problems on planar graphs

Brenda S. Baker · Journal of the ACM · 1994 · 973 citations · Full text

, , +15

A fast and simple randomized parallel algorithm for the maximal independent set problem

Noga Alon, László Babai, Alon Itai · Journal of Algorithms · 1986 · 842 citations

, , +13

On generating all maximal independent sets

David S. Johnson, Mihalis Yannakakis, Christos H. Papadimitriou · Information Processing Letters · 1988 · 768 citations

, , +5

Simple heuristics for unit disk graphs

Madhav Marathe, Heinz Breu, Harry B. Hunt et al. · Networks · 1995 · 494 citations

, , +17

Finding a Maximum Independent Set

Robert E. Tarjan, Anthony E. Trojanowski · SIAM Journal on Computing · 1977 · 474 citations

, , +10

1–5 of 263

Authors

555

  1. AA
    Anna Adamaszek

    University of Copenhagen, Denmark

    6 publications · 161 citations

    6

    h-index

  2. VT
    Vangélis Th. Paschos

    Université Paris Dauphine-PSL, France

    6 publications · 191 citations

    6

    h-index

  3. AW
    Andreas Wiese

    Technische Universität Berlin, Germany

    6 publications · 157 citations

    6

    h-index

  4. MM
    Magnús M. Halldórsson

    Reykjavík University, Iceland

    6 publications · 593 citations

    6

    h-index

  5. KC
    Keren Censor-Hillel

    Technion – Israel Institute of Technology, Israel

    6 publications · 157 citations

    6

    h-index

1–5 of 555

Institutions

285

  1. Tel Aviv University

    Tel Aviv, Israel

    10 h-index

    18 publications

    1.4K citations

  2. ETH Zurich

    Zurich, Switzerland

    8 h-index

    16 publications

    922 citations

  3. Massachusetts Institute of Technology

    Cambridge, United States

    8 h-index

    13 publications

    1.5K citations

  4. Technion – Israel Institute of Technology

    Haifa, Israel

    6 h-index

    10 publications

    1.1K citations

  5. Université Paris Dauphine-PSL

    Paris, France

    6 h-index

    13 publications

    474 citations

  6. Max Planck Society

    Munich, Germany

    6 h-index

    9 publications

    313 citations

  7. University of Waterloo

    Waterloo, Canada

    6 h-index

    7 publications

    441 citations

  8. AT&T (United States)

    Bedminster, United States

    6 h-index

    8 publications

    2.8K citations

1–8 of 285

Venues

  1. Information Processing Letters

    10 publications · 985 citations

    10

    h-index

  2. Discrete Applied Mathematics

    10 publications · 558 citations

    10

    h-index

  3. arXiv (Cornell University)

    Repository · 11 publications · 236 citations

    10

    h-index

  4. SIAM Journal on Computing

    8 publications · 799 citations

    8

    h-index

  5. Journal of Algorithms

    7 publications · 1.4K citations

    7

    h-index

1–5