Clustering and domination in perfect graphs |
| |
Authors: | DG Corneil Y Perl |
| |
Institution: | Department of Computer Science, University of Toronto, Toronto, Ont., Canada;Computer Science Department, Rutgers University, New Brunswick, NJ 08903, USA;Computer Science Department, Bar-Ilan University, Ramat-Gan, Israel |
| |
Abstract: | A k-cluster in a graph is an induced subgraph on k vertices which maximizes the number of edges. Both the k-cluster problem and the k-dominating set problem are NP-complete for graphs in general. In this paper we investigate the complexity status of these problems on various sub-classes of perfect graphs. In particular, we examine comparability graphs, chordal graphs, bipartite graphs, split graphs, cographs and κ-trees. For example, it is shown that the k-cluster problem is NP-complete for both bipartite and chordal graphs and the independent k-dominating set problem is NP-complete for bipartite graphs. Furthermore, where the k-cluster problem is polynomial we study the weighted and connected versions as well. Similarly we also look at the minimum k-dominating set problem on families which have polynomial k-dominating set algorithms. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|