3度图的最小顶点覆盖问题的多项式时间算法

作     者：支志兵 宁爱兵 胡琳琳 张惠珍 Zhi Zhibing;Ning Aibing;Hu Linlin;Zhang Huizhen

作者机构：上海理工大学管理学院上海200093 

基　　金：国家自然科学基金(71401106) 上海市一流学科建设项目资助(S1201YLXK) 高等学校博士学科点专项科研基金联合资助课题(20123120120005) 

出 版 物：《数学理论与应用》 (Mathematical Theory and Applications)

年 卷 期：2014年第34卷第3期

页      码：114-120页

摘      要：最小顶点覆盖问题是图论和组合数学中经典的NP-Hard问题之一,在实际问题中有着广泛的应用.本文首先给出最小顶点覆盖问题的若干性质,然后根据这些性质设计了3度图最小顶点覆盖问题的一个多项式时间算法,并通过2个实例对算法进行了说明.

主 题 词：最小顶点覆盖 多项式时间算法 

学科分类：07[理学] 070104[070104] 0701[理学-数学类] 

馆 藏 号：203443561...