標題: | 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-五月-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 toC-i. The generalized clique transversal problem is to determine the minimum cardinality of a subset D of V such that D boolean AND C-igreater 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/1288 |
ISSN: | 0166-218X |
DOI: | 10.1016/0166-218X(95)00048-V |
期刊: | DISCRETE APPLIED MATHEMATICS |
Volume: | 66 |
Issue: | 3 |
起始頁: | 189 |
結束頁: | 203 |
顯示於類別: | 期刊論文 |