Weighted Maximum-Clique Transversal Sets of Graphs. (26th January 2012) - Lee, Chuan-Min
Abstract : A maximum-clique transversal set of a graphG is a subset of vertices intersecting all maximum cliques ofG . The maximum-clique transversal set problem is to find a maximum-clique transversal set ofG of minimum cardinality. Motivated by the placement of transmitters for cellular telephones, Chang, Kloks, and Lee introduced the concept of maximum-clique transversal sets on graphs in 2001. In this paper, we study the weighted version of the maximum-clique transversal set problem for split graphs, balanced graphs, strongly chordal graph, Helly circular-arc graphs, comparability graphs, distance-hereditary graphs, and graphs of bounded treewidth.