Polynomial time algorithms for two classes of subgraph problem

作     者：Sridharan, Sriraman 

作者机构：Univ Perpignan Dept Math & Informat F-66100 Perpignan France 

出 版 物：《RAIRO-OPERATIONS RESEARCH》 (法国自动化、信息与运筹学；运筹学)

年 卷 期：2008年第42卷第3期

页      面：291-298页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主　　题：polynomial time algorithm NP-complete graph star regular graph perfect marching 

摘      要：We design a O(n(3)) polynomial time algorithm for finding a (k - 1)- regular subgraph in a k-regular graph without any induced star K(1,3)(claw-free). A polynomial time algorithm for finding a cubic subgraph in a 4-regular locally connected graph is also given. A family of k-regular graphs with an induced star K(1,3) (k even, k = 6), not containing any (k - 1)-regular subgraph is also constructed.