disjoint cycles

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

  • Ton Kloks
  • Chuan Min Lee
  • Jim Liu
    • Categories Graphs and Matroids Tags , , ,

    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. Citation Manuscript 4 July, 2001. Article Download View Feedback vertex sets and disjoint cycles in planar (di)graphs