On approximation properties of the independent set problem for low degree graphs
type: Item
instance of: scholarly article
title: On approximation properties of the independent set problem for low degree graphs
zbMATH Open document ID: 0916.68109
author: Piotr Berman
author: Toshihiro Fujito
published in: Theory of Computing Systems
publication date: 1999-03-22T00:00:00Z
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1268690
zbMATH Keywords: independent set problem
zbMATH Keywords: bounded node degree graphs
MaRDI profile type: Publication
full work available at URL: s002240000113
OpenAlex ID: W42852446
DOI: 10.1007/S002240000113
Recommended article: Structural Information and Communication Complexity
Recommended article: Greedy approximations of independent sets in low degree graphs
Recommended article: Q4400840
Recommended article: On approximation properties of the Independent set problem for degree 3 graphs
Recommended article: Improved approximations of independent sets in bounded-degree graphs
Recommended article: Approximating independent sets in sparse graphs
Recommended article: Approximating independent set in perturbed graphs
Recommended article: Q3128896
Recommended article: On approximation problems related to the independent set and vertex cover problems
Recommended article: On the complexity of approximating the independent set problem
description: scientific article; zbMATH DE number 1268690