Blar i Department of Informatics på forfatter "Fellows, Mike"
-
Finding k Disjoint Triangles in an Arbitrary Graph
Fellows, Mike; Heggernes, Pinar; Rosamond, Frances; Sloper, Christian; Telle, Jan Arne (Journal article; Peer reviewed, 2004)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 ...