On the complexity of approximating the independent set problem

DOI10.1007/BFb0028990zbMath1492.68060OpenAlexW1510300750MaRDI QIDQ5096160

Piotr Berman, Georg Schnitger

Publication date: 16 August 2022

Published in: STACS 89 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bfb0028990

zbMATH Keywords

approximation algorithmfeasible solutioncombinatorial optimization problempolynomial-time approximation schememaximization problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

Recent results in hardness of approximation ⋮ On the approximability of the maximum common subgraph problem ⋮ Maximum bounded 3-dimensional matching is MAX SNP-complete ⋮ An exact algorithm for the maximum clique problem ⋮ A note on the approximation of the MAX CLIQUE problem ⋮ Approximating maximum independent sets by excluding subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structure preserving reductions among convex optimization problems
• Toward a unified approach for the classification of NP-complete optimization problems
• Non deterministic polynomial optimization problems and their approximations
• Approximation algorithms for combinatorial problems
• The Complexity of Some Problems on Subsequences and Supersequences
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: On the complexity of approximating the independent set problem