Improved approximations for maximum independent set via approximation chains

DOI10.1016/S0893-9659(97)00044-XzbMATH Open0883.68067OpenAlexW2164654851MaRDI QIDQ1372278FDOQ1372278

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

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

zbMATH Keywords

maximum independent setNP-complete problem

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Cites Work

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

Cited In (13)

• Ultimate greedy approximation of independent sets in subcubic graphs
• Title not available (Why is that?)
• A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• Title not available (Why is that?)
• On-line models and algorithms for max independent set
• Polynomial approximation algorithms with performance guarantees: an introduction-by-example
• Improved distributed approximations for maximum independent set
• Filtering algorithms for the NValue constraint
• On the differential approximation of MIN SET COVER
• Improved (In-)Approximability Bounds for d-Scattered Set
• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
• 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)