Approximation algorithms for clique transversals on some graph classes

作     者：Lin, Min Chih Vasiliev, Saveliy 

作者机构：Univ Buenos Aires CONICET RA-1053 Buenos Aires DF Argentina Univ Buenos Aires FCEyN Inst Calculo RA-1053 Buenos Aires DF Argentina 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2015年第115卷第9期

页      面：667-670页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：UBACyT [20020130100800BA, 20020120100058] PICT ANPCyT [2010-1970, 2013-2205] 

主　　题：Approximation algorithms Clique transversal Graph classes NP-hard 

摘      要：Given a graph G = (V. E) a clique is a maximal subset of pairwise adjacent vertices of V of size at least 2. A clique transversal is a subset of vertices that intersects the vertex set of each clique of G. Finding a minimum-cardinality clique transversal is NP-hard for the following classes: planar, line and bounded degree graphs. For line graphs we present a 3-approximation for the unweighted case and a 4-approximation for the weighted case with nonnegative weights;a inverted right perpendicular(G) + 1)/2inverted left perpendicular-approximation for bounded degree graphs and a 3-approximation for planar graphs. (C) 2015 Elsevier B.V. All rights reserved.