A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
详细信息 查看全文
- 作者：Ekkehard Kö ; hlera ; ekkehard.koehler@b-tu.de" class="auth_mail" title="E-mail the corresponding author ; Lalla Mouatadidb ; lalla@cs.toronto.edu" class="auth_mail" title="E-mail the corresponding author
- 关键词：Maximum weight independent set ; Cocomparability graphs ; Posets ; Minimum weight vertex cover
- 刊名：Information Processing Letters
- 出版年：2016
- 出版时间：June 2016
- 年：2016
- 卷：116
- 期：6
- 页码：391-395
- 全文大小：272 K
文摘
- •
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.