کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427139 | 686455 | 2013 | 7 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A faster FPT algorithm for Bipartite Contraction A faster FPT algorithm for Bipartite Contraction](/preview/png/427139.png)
• We present an improved FPT algorithm for the Bipartite Contraction problem.
• The running time improves on an earlier double-exponential algorithm by Heggernes et al. (2011).
• The algorithm uses important separators and randomized coloring in a nontrivial way.
The Bipartite Contraction problem is to decide, given a graph G and a parameter k, whether we can obtain a bipartite graph from G by at most k edge contractions. The fixed-parameter tractability of the problem was shown by Heggernes et al. [13], with an algorithm whose running time has double-exponential dependence on k . We present a new randomized FPT algorithm for the problem, which is both conceptually simpler and achieves an improved 2O(k2)nm2O(k2)nm running time, i.e., avoiding the double-exponential dependence on k. The algorithm can be derandomized using standard techniques.
Journal: Information Processing Letters - Volume 113, Issues 22–24, November–December 2013, Pages 906–912