Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331913 | Information Processing Letters | 2015 | 5 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Zuosong Liang, Erfang Shan,