dc.contributor.author | Fellows, Mike | eng |
dc.contributor.author | Heggernes, Pinar | eng |
dc.contributor.author | Rosamond, Frances | eng |
dc.contributor.author | Sloper, Christian | eng |
dc.contributor.author | Telle, Jan Arne | eng |
dc.date.accessioned | 2006-03-01T15:57:29Z | |
dc.date.available | 2006-03-01T15:57:29Z | |
dc.date.issued | 2004 | eng |
dc.identifier.isbn | 3-540-24132-9 | en_US |
dc.identifier.issn | 0302-9743 | en_US |
dc.identifier.uri | https://hdl.handle.net/1956/1114 | |
dc.description.abstract | We consider the NP-complete problem of deciding whether an input graph on n vertices has k vertex-disjoint copies of a fixed graph H. For H=K 3 (the triangle) we give an O(22klog k + 1.869k n 2) algorithm, and for general H an O(2k|H|logk + 2k|H|log |H| n |H|) algorithm. We introduce a preprocessing (kernelization) technique based on crown decompositions of an auxiliary graph. For H=K 3 this leads to a preprocessing algorithm that reduces an arbitrary input graph of the problem to a graph on O(k 3) vertices in polynomial time. | |
dc.format.extent | 116308 bytes | eng |
dc.format.mimetype | application/pdf | eng |
dc.language.iso | eng | eng |
dc.publisher | Springer Verlag | en_US |
dc.title | Finding k Disjoint Triangles in an Arbitrary Graph | en_US |
dc.type | Journal article | |
dc.type | Peer reviewed | |
dc.description.version | acceptedVersion | en_US |
dc.rights.holder | Copyright 2004 Springer | |
dc.identifier.doi | https://doi.org/10.1007/978-3-540-30559-0_20 | |
dc.identifier.cristin | 424893 | |
dc.source.journal | Lecture Notes in Computer Science | |
dc.source.pagenumber | 235-244 | |
dc.identifier.citation | Lecture Notes in Computer Science vol 3353, 235-244. | |
dc.source.volume | 3353 | |