Genetic algorithmic approach to find the maximum weight independent set of a graph |
| |
| Authors: | Sk. Md. Abu Nayeem Madhumangal Pal |
| |
| Affiliation: | 1. Department of Mathematics, Jhargram Raj College, W.B., India
2. Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, W.B., India
|
| |
| Abstract: | In this paper, Genetic Algorithm (GA) is used to find the Maximum Weight Independent Set (MWIS) of a graph. First, MWIS problem is formulated as a 0-1 integer programming optimization problem with linear objective function and a single quadratic constraint. Then GA is implemented with the help of this formulation. Since GA is a heuristic search method, exact solution is not reached in every run. Though the suboptimal solution obtained is very near to the exact one. Computational result comprising an average performance is also presented here. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
