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 |
Fingerprint
Dive into the research topics of 'On disjoint cycles'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver