ON DISJOINT CYCLES

作     者：HANS L. BODLAENDER 

作者机构：Department of Computer Science University of Utrecht P.O. Box 80.089 3508 TB Utrecht the Netherlands 

出 版 物：《International Journal of Foundations of Computer Science》 

年 卷 期：1994年第5卷第1期

页      面：59-68页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Graph algorithms disjoint cycles in graphs minors feedback vertex set efficient algorithms 

摘      要：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 K 3 , has an membership test algorithm.