| dc.creator |
Mujuni, Egbert |
|
| dc.creator |
Rosamond, Frances |
|
| dc.date |
2016-09-21T12:38:36Z |
|
| dc.date |
2016-09-21T12:38:36Z |
|
| dc.date |
2008 |
|
| dc.date.accessioned |
2018-03-27T08:58:09Z |
|
| dc.date.available |
2018-03-27T08:58:09Z |
|
| dc.identifier |
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.. |
|
| dc.identifier |
http://hdl.handle.net/20.500.11810/3842 |
|
| dc.identifier.uri |
http://hdl.handle.net/20.500.11810/3842 |
|
| dc.description |
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. |
|
| dc.language |
en |
|
| dc.title |
Parameterized Complexity of the Clique Partition Problem |
|
| dc.type |
Journal Article, Peer Reviewed |
|