A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs

作者：Koehler Ekkehard; Mouatadid Lalla^*

来源：Information Processing Letters, 2016, 116(6): 391-395.

DOI：10.1016/j.ipl.2015.12.001

• Maximum weight independent set
• Cocomparability graphs
• Posets
• Minimum weight vertex cover

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(n(2)) 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) 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.

• 出版日期2016-6