文献类型：期刊文章

作　　者：张少强[1] 王继强[2] 李曙光[3]

机构地区：[1]山东大学数学与系统科学学院,山东济南250100 [2]山东财政学院文理学院,山东济南250014 [3]烟台大学数学与信息科学系,山东烟台264005

出　　处：《山东大学学报（理学版）》

基　　金：国家自然科学基金资助项目 ( 1 0 2 71 0 6 5 )

年　　份：2004

卷　　号：39

期　　号：1

起止页码：1-4

语　　种：中文

收录情况：BDHX、BDHX2000、CAS、CSA-PROQEUST、CSCD、CSCD2011_2012、IC、JST、MR、PROQUEST、RCCSE、RSC、ZGKJHX、ZMATH、核心刊

摘　　要：给定一个无向连通图G ,圈包装问题就是求G的边不相交圈的最大数目 .此问题在一般图下是APX困难问题 ,在平面图下是NP困难问题 .主要证明了在几类特殊的平面图下多项式时间可得到最优解 .主要考虑外平面图 ,系列平行图和平面欧拉图这三类特殊的平面图 .

关 键 词：包装  圈  多项式时间算法 外平面图 系列平行图 欧拉图

分 类 号：O157[数学类] TP301]