科研之友
微信
新浪微博
Facebook
分享链接
摘要
In this paper, we consider whether the vertices of graph G can be partitioned into K subsets V-1, V-2,... V-K so that for each i is an element of {1,...,K}, the subgraph induced by V-i is a perfect matching where K <= vertical bar V vertical bar. It is known that it is an NP complete problem in general graphs. In this paper, we restrict the problem in Halin graphs and give an algorithm to find the minimum value of K (2 <= K <= 4) in Halin graphs. The time complexity is O(n).
- 出版日期2007
- 单位中山大学
