The clique-transversal set problem in {claw,K4}-free planar graphs
详细信息 查看全文
- 作者：Zuosong Lianga ; Erfang Shanb ; c ; efshan@shu.edu.cn" class="auth_mail" title="E-mail the corresponding author ; Liying Kangc
- 关键词：Algorithms ; Graph algorithms ; Combinatorial problems
- 刊名：Information Processing Letters
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：118
- 期：Complete
- 页码：64-68
- 全文大小：543 K
文摘
- •
Clique-transversal set problem is to find a minimum clique-transversal set of graphs.
- •
Clique-transversal set problem (CTS) is proved to be NP-complete in planar graphs.
- •
We give a polynomial algorithm for the CTS problem in {claw,K4}-free planar graphs.