On the complexity of approximating the independent set problem

1992/01/01 by Piotr Berman, Georg Schnitger · 92 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computational complexity theory #Computer science #Constant (computer programming) #Discrete mathematics #Graph #Independent set #Mathematics #Optimization and Search Problems #Polynomial-time approximation scheme #Satisfiability #Scheme (mathematics) #Set (abstract data type) #Time complexity

paper · doi:10.1016/0890-5401(92)90056-l

published in Information and Computation 96(1), 77-94 (Elsevier BV)

crossref issued 1992/01/01 · crossref published 1992/01/01 · crossref published-print 1992/01/01 · openalex publication_date 1992/01/01 · crossref created 2004/12/16 · crossref deposited 2019/01/30 · openalex created_date 2025/10/10 · crossref indexed 2026/03/18 · openalex updated_date 2026/07/02

Citations

• Structure preserving reductions among convex optimization problems
• The Complexity of Some Problems on Subsequences and Supersequences
• Approximation algorithms for combinatorial problems
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

Cited by

• Clique is hard to approximate within n/sup 1-ε/
• Proof verification and the hardness of approximation problems
• Proof verification and hardness of approximation problems
• Improved hardness results for approximating the chromatic number
• Induced path [wikipedia]