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

GRAPH SEPARATION IS NP-COMPLETE FOR 3-REGULAR GRAPHS

作　　者：刁科凤[1] 李继乾[2] 王志雄[3] 周惠山 

机构地区：[1]山东大学数学与系统科学学院 [2]曲阜师范大学运筹所 [3]华侨大学数学系 [4]BellSouth Applied Technology,5250 Triangle Parkway,Norcross,Georgia30092,USA

出　　处：《系统科学与数学》2003年第1期30-37,共8页Journal of Systems Science and Mathematical Sciences

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

摘　　要：证明了3-正则图的最小平分问题和最小α-分割问题都是NP-完全问题.We prove that both the minimum bisection problem and minimum a-separation problem are NP-complete for 3-regular graphs.

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

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