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 mathmlsrc">mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0020019016301429&_mathId=si3.gif&_user=111111111&_pii=S0020019016301429&_rdoc=1&_issn=00200190&md5=56764aac882d8e84462115607a89b967" title="Click to view the MathML source">{claw,K4}mathContainer hidden">mathCode"><math altimg="si3.gif" overflow="scroll">
{ claw , mathvariant="normal">K 4 } math>-free planar graphs.