|
|||||
|
|
The clique-transversal set problem in claw-free graphs with degree at most 4 |
|
| Authors: | Zuosong Liang Erfang Shan |
| Affiliation: | 1. School of Management, Qufu Normal University, Rizhao 276826, China;2. School of Management, Shanghai University, Shanghai 200444, China;3. Department of Mathematics, Shanghai University, Shanghai 200444, China |
| Abstract: | A clique of a graph G is defined as a complete subgraph maximal under inclusion and having at least two vertices. A clique-transversal set D of G is a subset of vertices of G such that D meets all cliques of G. The clique-transversal set problem is to find a minimum clique-transversal set of G. In this paper we present a polynomial time algorithm for the clique-transversal set problem on claw-free graphs with degree at most 4. |
| Keywords: | Graph algorithms Clique Clique-transversal set problem Polynomial time algorithm Claw-free graph |
| 本文献已被 ScienceDirect 等数据库收录！ | |