Improved approximations for maximum independent set via approximation chains
type: Item
instance of: scholarly article
title: Improved approximations for maximum independent set via approximation chains
zbMATH Open document ID: 0883.68067
DOI: 10.1016/S0893-9659(97)00044-X
published in: Applied Mathematics Letters
publication date: 1998-03-16T00:00:00Z
Mathematics Subject Classification ID: 68W10
zbMATH DE Number: 1085370
zbMATH Keywords: NP-complete problem
zbMATH Keywords: maximum independent set
author: Marc Demange
author: Vangelis Th. Paschos
MaRDI profile type: Publication
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
cites work: Greed is good: approximating independent sets in sparse and bounded-degree graphs
cites work: Q4698692
cites work: Q3128896
cites work: Vertex packings: Structural properties and algorithms
cites work: On Turan's theorem for sparse graphs
cites work: On Syntactic versus Computational Views of Approximability
cites work: A note on the independence number of triangle-free graphs
cites work: A note on the independence number of triangle-free graphs. II
cites work: Q5781249
cites work: Three short proofs in graph theory
cites work: On Approximate Solutions for Combinatorial Optimization Problems
full work available at URL: s0893-9659(97)00044-x
OpenAlex ID: W2164654851
description: scientific article; zbMATH DE number 1085370