Weighted maximum-clique transversal sets of graphs (Q410660): Difference between revisions
From MaRDI portal
Revision as of 00:45, 5 July 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Weighted maximum-clique transversal sets of graphs |
scientific article |
Statements
Weighted maximum-clique transversal sets of graphs (English)
0 references
3 April 2012
0 references
Summary: A maximum-clique transversal set of a graph \(G\) is a subset of vertices intersecting all maximum cliques of \(G\). The maximum-clique transversal set problem is to find a maximum-clique transversal set of \(G\) of minimum cardinality. Motivated by the placement of transmitters for cellular telephones, \textit{M.-S. Chang}, \textit{T. Kloks} and \textit{C.-M. Lee} [Lect. Notes Comput. Sci. 2204, 32--43 (2001; Zbl 1042.68619)] introduced the concept of maximum-clique transversal sets on graphs. 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.
0 references
split graphs
0 references
balanced graphs
0 references
strongly chordal graph
0 references
Helly circular-arc graphs
0 references
comparability graphs
0 references
distance-hereditary graphs
0 references
graphs of bounded treewidth
0 references
0 references
