Parameterized Complexity of the Clique Partition Problem
| dc.contributor.author | Mujuni, Egbert | |
| dc.contributor.author | Rosamond, Frances | |
| dc.date.accessioned | 2016-09-21T12:38:36Z | |
| dc.date.available | 2016-09-21T12:38:36Z | |
| dc.date.issued | 2008 | |
| dc.description.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. | en_US |
| dc.identifier.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.. | en_US |
| dc.identifier.uri | http://hdl.handle.net/20.500.11810/3842 | |
| dc.language.iso | en | en_US |
| dc.title | Parameterized Complexity of the Clique Partition Problem | en_US |
| dc.type | Journal Article, Peer Reviewed | en_US |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Parameterized Complexity of the Clique Partition Problem.pdf
- Size:
- 144.22 KB
- Format:
- Adobe Portable Document Format
- Description:
- Full text
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- license.txt
- Size:
- 1.71 KB
- Format:
- Item-specific license agreed upon to submission
- Description: