最小填充问题的可分解性

• 作者: 张振坤 林诒勋 王秀梅
• 来源期刊: 应用数学
• 学科: 数学
• 关键词: 图标号 填充数 弦图 分解定理
• 年，卷（期）: 2008,（2）
• 页码范围: 354-361
• 页数: 8页
• 分类号: O157.5
• 字数: 2882字
• 语种: 中文

摘要

起源于稀疏矩阵计算和其它应用领域的图G的最小填充问题是在图G中寻求一个内含边数最小的边集F使得G+F是弦图.这里最小值|F|称为图G的填充数,表示为f(G).作为NP-困难问题,该问题的降维性质已被研究,其中包括它的可分解性.基本的可分解定理是:如果图G的一个点割集S是一个团,则G经由S是可分解的.作为推广,如果S是一个"近似"团(即只有极少数边丢失的团),则G经由S是可分解的.本文首先给出基本分解定理的另外一个推广:如果S是G的一个极小点割集且G-S含有至少|S|个分支,则G经由S是可分解的;其次,给出了这个新推广定理的一些应用.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张振坤	黄淮学院数学系	22	22	3.0	3.0
2	王秀梅	郑州大学数学系	11	15	2.0	2.0
3	林诒勋	郑州大学数学系	23	162	7.0	12.0