.png){kind=icon}
.png){kind=icon}
Return
A simple approximation algorithm for WIS based on the approximability in k-partite graphs
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2005.01.058.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this note, simple approximation algorithms for the weighted independent set problem are presented with a performance ratio depending on Delta(G). These algorithms do not improve the best approximation algorithm known so far for this problem but they are of interest because of their simplicity. Precisely, we show how an optimum weighted independent set in bipartite graphs and a rho-approximation of WIS in k-partite graphs respectively allows to obtain a 2/Delta(G) approximation and a k/Delta(G) rho-approximation in general graphs. Note that the ratio 2/Delta(G) is the best bound known for the particular cases Delta(G) = 3 or Delta(G) = 4. (c) 2005 Elsevier B.V. All rights reserved.
Keywords:
graph algorithms
approximation algorithms
combinatorial optimization
coloring
weighted independent set
k-partite graphs
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
No organization information available