Improved approximations for maximum independent set via approximation chains
From MaRDI portal
Publication:1372278
DOI10.1016/S0893-9659(97)00044-XzbMath0883.68067OpenAlexW2164654851MaRDI QIDQ1372278
Vangelis Th. Paschos, Marc Demange
Publication date: 16 March 1998
Published in: Applied Mathematics Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0893-9659(97)00044-x
Related Items (8)
On an approximation measure founded on the links between optimization and polynomial approximation theory ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ Filtering algorithms for the NValue constraint ⋮ A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem ⋮ Improved (In-)Approximability Bounds for d-Scattered Set ⋮ On the differential approximation of MIN SET COVER ⋮ Polynomial approximation algorithms with performance guarantees: an introduction-by-example ⋮ On-line models and algorithms for max independent set
Cites Work
- A note on the independence number of triangle-free graphs
- Efficient bounds for the stable set, vertex cover and set packing problems
- On Turan's theorem for sparse graphs
- A note on the independence number of triangle-free graphs. II
- A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
- Three short proofs in graph theory
- Greed is good
- On Approximate Solutions for Combinatorial Optimization Problems
- Vertex packings: Structural properties and algorithms
- On Syntactic versus Computational Views of Approximability
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Improved approximations for maximum independent set via approximation chains
