Abstract
It is shown, that for each constant k≥1, the following problems can be solved in time: given a graph G, determine whether G has k vertex disjoint cycles, determine whether G has k edge disjoint cycles, determine whether G has a feedback vertex set of size ≤k. Also, every class , that is closed under minor taking, taking, and that does not contain the graph consisting of k disjoint copies of K3, has an membership test algorithm.
| Original language | English |
|---|---|
| Pages (from-to) | 59-68 |
| Journal | International Journal of Foundations of Computer Science |
| Volume | 5 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 1994 |