A Linear Kernel for the k -Disjoint Cycle Problem on Planar Graphs Export

@incollection{citeulike:4943821, abstract = {We consider the following problem: given a planar graph G = (V,E) and integer k, find if possible at least k vertex disjoint cycles in G. This problem is known to be NP-complete. In this paper, we give a number of simple data reduction rules. Each rule transforms the input to an equivalent smaller input, and can be carried out in polynomial time. We show that inputs on which no rule can be carried out have size linear in k. Thereby we obtain that the k -Disjoint Cycles problem on planar graphs has a kernel of linear size. We also present a parameterized algorithm with a running time of .}, author = {Bodlaender, Hans and Penninkx, Eelko and Tan, Richard}, citeulike-article-id = {4943821}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-92182-0_29}, citeulike-linkout-1 = {http://www.springerlink.com/content/211l3p182450001u}, doi = {10.1007/978-3-540-92182-0_29}, journal = {Algorithms and Computation}, keywords = {algorithms, graph, parameterized}, pages = {306--317}, posted-at = {2009-06-24 13:46:07}, priority = {2}, title = {A Linear Kernel for the k -Disjoint Cycle Problem on Planar Graphs}, url = {http://dx.doi.org/10.1007/978-3-540-92182-0_29}, year = {2008} }

TY - CHAP ID - citeulike:4943821 L3 - citeulike-article-id:4943821 N2 - We consider the following problem: given a planar graph G = (V,E) and integer k, find if possible at least k vertex disjoint cycles in G. This problem is known to be NP-complete. In this paper, we give a number of simple data reduction rules. Each rule transforms the input to an equivalent smaller input, and can be carried out in polynomial time. We show that inputs on which no rule can be carried out have size linear in k. Thereby we obtain that the k -Disjoint Cycles problem on planar graphs has a kernel of linear size. We also present a parameterized algorithm with a running time of . JF - Algorithms and Computation EP - 317 TI - A Linear Kernel for the k -Disjoint Cycle Problem on Planar Graphs SP - 306 KW - algorithms KW - graph KW - parameterized AU - Bodlaender, Hans AU - Penninkx, Eelko AU - Tan, Richard PY - 2008/// UR - http://dx.doi.org/10.1007/978-3-540-92182-0_29 ER -