咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Polynomial time algorithms for... 收藏

Polynomial time algorithms for two classes of subgraph problem

为 subgraph 问题的二个班的多项式时间算法

作     者: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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分