Improved approximations for maximum independent set via approximation chains

DOI10.1016/S0893-9659(97)00044-XMaRDI QIDQ1372278zbMATH OpenOpenAlexFDO

Authors Marc Demange, Vangelis Th. Paschos

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

zbMATH Keywords

maximum independent setNP-complete problem

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Recommendations

• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
• scientific article; zbMATH DE number 792644
• scientific article; zbMATH DE number 1003268
• Improved approximations of independent sets in bounded-degree graphs
• scientific article; zbMATH DE number 753971

Cites work

• scientific article; zbMATH DE number 1003268 (Why is no real title available?)
• scientific article; zbMATH DE number 753971 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
• A note on the independence number of triangle-free graphs
• A note on the independence number of triangle-free graphs. II
• Efficient bounds for the stable set, vertex cover and set packing problems
• Greed is good: approximating independent sets in sparse and bounded-degree graphs
• On Approximate Solutions for Combinatorial Optimization Problems
• On Syntactic versus Computational Views of Approximability
• On Turan's theorem for sparse graphs
• Three short proofs in graph theory
• Vertex packings: Structural properties and algorithms

Cited in

(13)

• Ultimate greedy approximation of independent sets in subcubic graphs
• A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem
• scientific article; zbMATH DE number 1330075 (Why is no real title available?)
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• scientific article; zbMATH DE number 792644 (Why is no real title available?)
• Polynomial approximation algorithms with performance guarantees: an introduction-by-example
• On-line models and algorithms for max independent set
• Improved distributed approximations for maximum independent set
• Filtering algorithms for the NValue constraint
• On the differential approximation of MIN SET COVER
• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
• Improved (In-)Approximability Bounds for d-Scattered Set
• Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation

This page was built for publication: Improved approximations for maximum independent set via approximation chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1372278)