Feedback vertex sets and disjoint cycles in planar (di)graphs

Ton Kloks (toncs.rhul.ac.uk)
C.M. Lee (cmleecs.ccu.edu.tw)
Jim Liu (liucs.uleth.ca)

Abstract: We present new fixed parameter algorithms for feedback vertex set and disjoint cycles on planar graphs. We give an $O(c^{\sqrt{k}} + n)$ algorithm for $k$-feedback vertex set and an $O(c^{\sqrt{k}} n)$ algorithm for $k$-disjoint cycles on planar graphs.

Keywords: planar graph, fixed parameter complexity, disjoint cycles, feedback vertex set

Category 1: Combinatorial Optimization (Graphs and Matroids )

Citation: Manuscript 4 July, 2001.

Download: [Postscript]

Entry Submitted: 07/04/2001
Entry Accepted: 07/04/2001
Entry Last Modified: 07/04/2001

Modify/Update this entry