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

  • Ton Kloks
  • Chuan Min Lee
  • Jim Liu
    • Categories Graphs and Matroids Tags , , , Short URL: https://optimization-online.org/?p=8768

    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