Weighted Maximum-Clique Transversal Sets of Graphs. (26th January 2012)

• Record Type: Journal Article
• Authors: Lee, Chuan-Min
• Other Names: Cheng E. Academic Editor.; Pêcher A. Academic Editor.; Tomita E. Academic Editor.
• Is Part Of: ISRN discrete mathematics. Volume 2011(2011)
• Publication Date: 2012-01-26
• Subjects: Discrete mathematics -- Periodicals; Computer science -- Mathematics; Computer science -- Mathematics; Periodicals; 511.1
• DOI: 10.5402/2011/540834
• Languages: English
• ISSNs: 2090-7788

Abstract

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.