| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427033 | Information Processing Letters | 2016 | 5 Pages |
•Maximum weight independent set on cocomparability graphs.•Linear time algorithm, does not compute the complement or the corresponding poset.•Algorithm exploits the vertex ordering characterization of cocomparability graphs.•Linear time minimum weight vertex cover for cocomparability graphs as a corollary.
The maximum weight independent set (WMIS) problem is a well-known NP-hard problem. It is a generalization of the maximum cardinality independent set problem where all the vertices have identical weights. There is an O(n2)O(n2) time algorithm to compute a WMIS for cocomparability graphs by computing a maximum weight clique on the corresponding complement of the graph [1]. We present the first O(m+n)O(m+n) time algorithm to compute a WMIS directly on the given cocomparability graph, where m and n are the number of edges and vertices of the graph respectively. As a corollary, we get the minimum weight vertex cover of a cocomparability graph in linear time as well.
