Approximation Algorithms on k-Cycle Transversal and k-Clique Transversal  

作　　者：Zhong-Zheng Tang Zhuo Diao 

机构地区：[1]School of Science,Beijing University of Posts and Telecommunications,Beijing 100876,China [2]School of Statistics and Mathematics,Central University of Finance and Economics,Beijing 100081,China

出　　处：《Journal of the Operations Research Society of China》2021年第4期883-892,共10页中国运筹学会会刊（英文）

基　　金：the National Natural Science Foundation of China(No.11901605);the disciplinary funding of Central University of Finance and Economics.

摘　　要：Given a weighted graph G=(V,E)with weight w:E→Z+,a k-cycle transversal is an edge subset A of E such that G−A has no k-cycle.The minimum weight of kcycle transversal is the weighted transversal number on k-cycle,denoted byτk(Gw).In this paper,we design a(k−1/2)-approximation algorithm for the weighted transversal number on k-cycle when k is odd.Given a weighted graph G=(V,E)with weight w:E→Z+,a k-clique transversal is an edge subset A of E such that G−A has no k-clique.The minimum weight of k-clique transversal is the weighted transversal number on k-clique,denoted byτapproximation algorithm for the weighted transversal number on k(Gw).In this paper,we design a(k2−k−1)/2-k-clique.Last,we discuss the relationship between k-clique covering and k-clique packing in complete graph Kn.

关 键 词：k-cycle transversal k-clique transversal Approximation algorithms 

分 类 号：O15[理学—数学]