偶图的补图的侧廓问题和填充问题的NP-完全性(英文) 被引量：4

NP-completeness of the Profile Problem and the Fill-in Problem on Cobipartite Graphs

导出

摘要本文研究偶补图的侧廓问题和填充问题的计算复杂性，证明了：即使对直径不超过2的偶补图，侧廓问题和填充问题也是NP－完全的． The computational complexity of the profile problem and the fill-in problem is studiedin this paper. Our main results are as follows: The profile problem and the fill-in problem are NPcomplete even for cobipartite graphs with diaxneter at most 2.

作者原晋江林诒勋刘岩王世英

机构地区郑州大学数学系新疆大学经济所

出处《数学研究》 CSCD 1998年第3期239-243,共5页 Journal of Mathematical Study

关键词 NP-完全补图偶图计算复杂性证明直径填充问题 Chordal, Interval, Cobipartite, Profile, Fill-in

分类号 O157.5 [理学—数学]

引文网络
相关文献

同被引文献10

1林詒勋,原晋江.PROFILE MINIMIZATION PROBLEM FOR MATRICES AND GRAPHS[J].Acta Mathematicae Applicatae Sinica,1994,10(1):107-112. 被引量：4
2原晋江.图的填充和运算[J].中国科学（A辑）,1994,24(10):1021-1028. 被引量：11
3李文权,林诒勋.图的最小填充的分解定理[J].应用数学与计算数学学报,1994,8(1):39-46. 被引量：21
4张振坤,王秀梅,林诒勋.弦图的补图的最小填充(英文)[J].应用数学,2006,19(3):554-560. 被引量：2
5吴力,魏紫銮.图论在稀疏对称矩阵中的应用[J].数学的实践与认识,1990,20(2):52-62. 被引量：6
6YUAN Jinjiang (Department of Mathematics,Zhengzhou University, Zhengzhou 450052, China)ZHANG Heping (Department of Mathematics,Lanzhou University, Lanzhou 730000, China).MINIMUM FILL-IN PROBLEM OF GRAPHS[J].Systems Science and Mathematical Sciences,1996,9(3):193-197. 被引量：1
7LIN Yixun,YUAN Jinjiang(Department of Mathematics, Zhengzhou University, Zhengzhou 450052, China).MINIMUM PROFILE OF GRID NETWORKS[J].Systems Science and Mathematical Sciences,1994,7(1):56-66. 被引量：2
8林诒勋.图的填充问题的约化[J].应用数学,2000,13(3):111-114. 被引量：9
9林诒勋.图的扩张与稀疏矩阵计算中的若干优化问题(英文)[J].数学进展,2001,30(1):9-21. 被引量：7
10林诒勋.图的树宽的结构性结果(英文)[J].数学进展,2004,33(1):75-86. 被引量：5

引证文献4

1张振坤.树的补图的区间图完全化问题(英文)[J].应用数学,2009,22(1):48-55.
2万志超,冯爱芬.平面格子图P_m×P_n的最小填充[J].重庆科技学院学报（自然科学版）,2009,11(4):171-173.
3侯亚林,张振坤,李学志.树的线图的图扩充问题[J].数学的实践与认识,2009,39(16):252-259.
4ZHANG Zhen-kun,YU Min.The Interval Graph Completion Problem on Split Graphs[J].Chinese Quarterly Journal of Mathematics,2015,30(2):308-316.

1杨爱民.（m,n）——构形的侧廓[J].山西大学学报（自然科学版）,1996,19(1):22-26.
2张志立,李文权.证明NP—完全性的技巧[J].许昌师专学报,1994,13(2):53-55.
3侯亚林,张振坤,李学志.树的线图的图扩充问题[J].数学的实践与认识,2009,39(16):252-259.
4郝建修.侧廓问题的运算(英文)[J].河南科学,2008,26(11):1310-1313.
5郝建修.图的侧廓问题的一些界(英文)[J].河南科学,2007,25(2):194-196. 被引量：1
6张振坤.树的补图的区间图完全化问题(英文)[J].应用数学,2009,22(1):48-55.
7张振坤,高建来.4直径树线图的区间图扩充问题[J].河南科技大学学报（自然科学版）,2010,31(4):84-87.
8原晋江.图的弱准带宽和前沿带宽[J].中国科学（A辑）,1995,25(11):1121-1129. 被引量：1
9张同全,李伟东,李建平.限制的星划分问题[J].云南大学学报（自然科学版）,2008,30(2):109-112. 被引量：1

数学研究

1998年第3期

浏览历史

内容加载中请稍等...

偶图的补图的侧廓问题和填充问题的NP-完全性(英文) 被引量：4

同被引文献10

引证文献4

相关作者

相关机构

相关主题

浏览历史