{"title":"Approximating Maximum Weighted Independent Set Using Vertex Support","authors":"S. Balaji, V. Swaminathan, K. Kannan","country":null,"institution":"","volume":35,"journal":"International Journal of Mathematical and Computational Sciences","pagesStart":963,"pagesEnd":969,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/12153","abstract":"The Maximum Weighted Independent Set (MWIS)\r\nproblem is a classic graph optimization NP-hard problem. Given an\r\nundirected graph G = (V, E) and weighting function defined on the\r\nvertex set, the MWIS problem is to find a vertex set S V whose total\r\nweight is maximum subject to no two vertices in S are adjacent. This\r\npaper presents a novel approach to approximate the MWIS of a graph\r\nusing minimum weighted vertex cover of the graph. Computational\r\nexperiments are designed and conducted to study the performance\r\nof our proposed algorithm. Extensive simulation results show that\r\nthe proposed algorithm can yield better solutions than other existing\r\nalgorithms found in the literature for solving the MWIS.","references":null,"publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 35, 2009"}