On the complexity of approximating the independent set problem
From MaRDI portal
Publication:1184733
DOI10.1016/0890-5401(92)90056-LzbMath0804.90121OpenAlexW2053651631MaRDI QIDQ1184733
Publication date: 28 June 1992
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(92)90056-l
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (37)
The biclique k-clustering problem in bipartite graphs and its application in bioinformatics ⋮ Near-optimal nonapproximability results for some \textsc{Npo} PB-complete problems ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Approximation of Constraint Satisfaction via local search ⋮ On constructing an optimal consensus clustering from multiple clusterings ⋮ The complexity and approximability of finding maximum feasible subsystems of linear relations ⋮ Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function ⋮ On the analysis of optimization problems in arc-dependent networks ⋮ Approximating the independence number via the \(\vartheta\)-function ⋮ Kernel bounds for path and cycle problems ⋮ Analyzing read-once cutting plane proofs in Horn systems ⋮ Structure in approximation classes ⋮ Reachability in choice networks ⋮ Unit read-once refutations for systems of difference constraints ⋮ Expander graphs and their applications ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Unnamed Item ⋮ On approximating the \(d\)-girth of a graph ⋮ A survey on the structure of approximation classes ⋮ The approximation of maximum subgraph problems ⋮ Polynomially bounded minimization problems which are hard to approximate ⋮ Optimization, approximation, and complexity classes ⋮ Solving the maximum edge biclique packing problem on unbalanced bipartite graphs ⋮ Approximate solution of NP optimization problems ⋮ Complexities of efficient solutions of rectilinear polygon cover problems ⋮ Tilt assembly: algorithms for micro-factories that build objects with uniform external forces ⋮ On approximating the longest path in a graph ⋮ Approximating maximum independent sets by excluding subgraphs ⋮ Inapproximability results for the lateral gene transfer problem ⋮ On approximating the longest path in a graph ⋮ Hardness and methods to solve CLIQUE ⋮ On approximating four covering and packing problems ⋮ Zero knowledge and the chromatic number ⋮ Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas ⋮ On the hardness of approximating max-satisfy ⋮ Derandomized graph products ⋮ Clique is hard to approximate within \(n^{1-\epsilon}\)
Cites Work
- Unnamed Item
- Unnamed Item
- 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
