节点文献

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

GRAPH SEPARATION IS NP-COMPLETE FOR 3-REGULAR GRAPHS

推荐 CAJ下载
PDF下载
不支持迅雷等下载工具，请取消加速工具后下载。

【Author】 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 Technology； 5250 Triangle Parkway； Norcross； Georgia30092； USA 济南250100 临沂师范学院数学系；临沂276005；曲阜 273165；福建泉州 362011；

【摘要】证明了3-正则图的最小平分问题和最小α-分割问题都是NP-完全问题.更多还原

【Abstract】 We prove that both the minimum bisection problem and minimum a-separation problem are NP-complete for 3-regular graphs.更多还原

【关键词】 NP-完全问题；图的最小平分问题；图的最小α-分割问题；
【Key words】 NP-complete. minimum bisection problem； minimum a- separation problem.；

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

【文献出处】系统科学与数学 ,Journal of Systems Science and Mathematical Sciences , 编辑部邮箱 ,2003年01期

【分类号】O157.5
【下载频次】137

知网节下载

节点文献中：

本文链接的文献网络图示:

本文的引文网络

节点文献