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.