Parameterized Complexity of the Clique Partition Problem
Loading...
Date
2008
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The problem of deciding whether the edge-set of a
given graph can be partitioned into at most k cliques
is well known to be NP-complete. In this paper we
investigate this problem from the point of view of parameterized
complexity. We show that this problem
is fixed parameter tractable if we choose the number
of cliques as parameter. In particular, we show that
in polynomial time, a kernel bounded by k
2
can be
obtained, where k is the number of cliques. We also
give an O(2((k+3) log k)/2n) algorithm for this problem
in K4-free graphs.
Description
Keywords
Citation
Mujuni, E. and Rosamond, F., 2008, January. Parameterized complexity of the clique partition problem. In Proceedings of the fourteenth symposium on Computing: the Australasian theory-Volume 77 (pp. 75-78). Australian Computer Society, Inc..