Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419807 | Discrete Applied Mathematics | 2012 | 6 Pages |
Abstract
The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n3)O(n3)-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n4)O(n4)-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
M. Basavaraju, L.S. Chandran, T. Karthick,