版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.