3-正则图的分割问题是NP-完全问题

作     者：刁科凤 李继乾 王志雄 周惠山 Diao Kefeng (Department of Mathematics, Shandong University, Jinan 250100)Li Jiqian (Institute of Operations Research, Qufu Normal University, Qufu 273165)Wang Zhixiong (Department of Mathematics, Huaqiao Universit, Quanzhou, Fujian 362011)Zhou Huishan (BellSouth Applied Technology, 5250 Triangle Parkway, Norcross, Georgia, 30092, USA)

作者机构：山东大学数学与系统科学学院 曲阜师范大学运筹所 华侨大学数学系 BellSouth Applied Technology5250 Triangle ParkwayNorcrossGeorgia30092USA 

出 版 物：《系统科学与数学》 (Journal of Systems Science and Mathematical Sciences)

年 卷 期：2003年第23卷第1期

页      面：30-37页

核心收录：

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

基　　金：国家自然科学基金(60172003) 山东省自然科学基金(Z2000A02)资助课题 

主　　题：3-正则图 NP-完全问题 图 最小平分问题 最小α-分割问题 

摘      要：证明了3-正则图的最小平分问题和最小α-分割问题都是NP-完全问题.