標題: Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
作者: Chang, MS
Chen, YH
Chang, GJ
Yan, JH
應用數學系
Department of Applied Mathematics
關鍵字: clique-transversal set;neighborhood number;domination;dual;chordal graph;strongly chordal graph;k-tree;split graph;undirected path graph
公開日期: 20-May-1996
摘要: Suppose G=(V,E) is a graph in which each maximal clique C-i is associated with an integer r(i), where 0 less than or equal to r(i) less than or equal to\C-i\. The generalized clique transversal problem is to determine the minimum cardinality of a subset D of V such that \D boolean AND C-i\greater than or equal to r(i) for every maximal clique C-i of G. The problem includes the clique-transversal problem, the i,1 clique-cover problem, and for perfect graphs, the maximum q-colorable subgraph problems as special cases. This paper gives complexity results for the problem on subclasses of chordal graphs, e.g., strongly chordal graphs, k-trees, split graphs, and undirected path graphs.
URI: http://dx.doi.org/10.1016/0166-218X(95)00048-V
http://hdl.handle.net/11536/149205
ISSN: 0166-218X
DOI: 10.1016/0166-218X(95)00048-V
期刊: DISCRETE APPLIED MATHEMATICS
Volume: 66
起始頁: 189
結束頁: 203
Appears in Collections:Articles