A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
From MaRDI portal
Publication:1195856
DOI10.1016/0020-0190(92)90248-TzbMath0755.68073MaRDI QIDQ1195856
Publication date: 4 January 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items
A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem, On the performance guarantee of neural networks for NP-hard optimization problems, A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem, Improved approximations for maximum independent set via approximation chains, Extracting pure network submatrices in linear programs using signed graphs., The maximum balanced subgraph of a signed graph: applications and solution approaches, Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs
Cites Work