A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem

DOI10.1016/0020-0190(92)90248-TzbMath0755.68073MaRDI QIDQ1195856

Vangelis Th. Paschos

Publication date: 4 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

independent setapproximation algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Related Items (7)

A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem ⋮ Improved approximations for maximum independent set via approximation chains ⋮ A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem ⋮ Extracting pure network submatrices in linear programs using signed graphs. ⋮ On the performance guarantee of neural networks for NP-hard optimization problems ⋮ Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs ⋮ The maximum balanced subgraph of a signed graph: applications and solution approaches

Cites Work

• On Approximate Solutions for Combinatorial Optimization Problems
• Unnamed Item
• Unnamed Item

This page was built for publication: A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem