|
|||||
|
|
| 3-正则图的分割问题是NP-完全问题 | |
| 引用本文： | 刁科凤,李继乾,王志雄,周惠山.3-正则图的分割问题是NP-完全问题[J].系统科学与数学,2003,23(1):030-037. |
| 作者姓名： | 刁科凤 李继乾 王志雄 周惠山 |
| 作者单位： | 1. 山东大学数学与系统科学学院,济南,250100;临沂师范学院数学系,临沂,276005 2. 曲阜师范大学运筹所,曲阜,273165 3. 华侨大学数学系,福建,泉州,362011 4. BellSouth Applied Technology,5250 Triangle Parkway,Norcross,Georgia,30092,USA |
| 基金项目： | 国家自然科学基金(60172003)，山东省自然科学基金(Z2000A02)资助课题 |
| 摘 要： | 证明了3-正则图的最小平分问题和最小α-分割问题都是NP-完全问题. |
| 关 键 词： | NP-完全问题 图的最小平分问题 图的最小α-分割问题 |
| 修稿时间： | 2001年2月8日 |
GRAPH SEPARATION IS NP-COMPLETE FOR 3-REGULAR GRAPHS |
|
| Diao Kefeng.GRAPH SEPARATION IS NP-COMPLETE FOR 3-REGULAR GRAPHS[J].Journal of Systems Science and Mathematical Sciences,2003,23(1):030-037. | |
| Authors: | Diao Kefeng |
| Institution: | (1)Department of Math.Shandong Univ.Jinan 250100,P.R.China;(2)Inst.of Operations Research,Qufu Normal Univ.Qufu 273165,P.R.China;(3)Dept.of Math.Huaqiao Univ.Quanzhou,Fujian 362011,P.R.China;(4)BellSouth Applied Technology, 5250 Triangle Parkway,Norcross,Georgia,30092,USA |
| Abstract: | We prove that both the minimum bisection problem and minimum a-separation problem are NP-complete for 3-regular graphs. |
| Keywords: | NP-complete minimum bisection problem minimum a- separation problem |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 | |
| 点击此处可从《系统科学与数学》下载免费的PDF全文 | |