Parameterized complexity of the clique partition problem

Title: Parameterized complexity of the clique partition problem
Creator: Mujuni, Egbert; Rosamond, Frances
Relation: Fourteenth Computing: The Australasian Theory Symposium (CATS 2008). Theory of Computing: Proceedings of the Fourteenth Computing: The Australasian Theory Symposium (CATS 2008) (Wollongong, N.S.W 22-25 January, 2008) p. 75-78
Relation: http://www.acs.org.au/index.cfm?action=show&conID=200801081430444898
Publisher: Australian Computer Society
Resource Type: conference paper
Date: 2008
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² can be obtained, where k is the number of cliques. We also give an O(2⁽⁽k⁺³⁾ log k⁾/²n) algorithm for this problem in K₄-free graphs.
Subject: parametized compexity; clique partition; k cliques
Identifier: http://hdl.handle.net/1959.13/45123
Identifier: uon:6021
Identifier: ISBN:9781920682583
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format