Approximation algorithms for the weighted independent set problem in sparse graphs
type: Item
instance of: scholarly article
title: Approximation algorithms for the weighted independent set problem in sparse graphs
zbMATH Open document ID: 1173.05352
author: A. Kako
author: Takao Ono
author: Tomio Hirata
author: Magnús M. Halldórsson
published in: Discrete Applied Mathematics
publication date: 2009-06-30T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 5572542
zbMATH Keywords: weighted independent set problem
zbMATH Keywords: approximation algorithm
zbMATH Keywords: weighted degree
MaRDI profile type: Publication
full work available at URL: j.dam.2008.08.027
OpenAlex ID: W2103011134
cites work: Proof verification and the hardness of approximation problems
cites work: On approximation properties of the independent set problem for low degree graphs
cites work: Improved approximations for weighted and unweighted graph problems
cites work: Geometric algorithms and combinatorial optimization.
cites work: Approximations of Weighted Independent Set and Hereditary Subset Problems
cites work: Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
cites work: Greed is good: Approximating independent sets in sparse and bounded-degree graphs
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: Approximate graph coloring by semidefinite programming
cites work: Smallest-last ordering and clustering and graph coloring algorithms
cites work: Vertex packings: Structural properties and algorithms
cites work: A note on greedy algorithms for the maximum weighted independent set problem
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
DOI: 10.1016/J.DAM.2008.08.027
description: scientific article; zbMATH DE number 5572542