| 3－正则3－连通无爪平面图的Hamilton圈问题和Hamilton路问题的NP－完全性 |
| |
| 引用本文： | 原晋江.3－正则3－连通无爪平面图的Hamilton圈问题和Hamilton路问题的NP－完全性[J].新疆大学学报(理工版),1994(3). |
| |
| 作者姓名： | 原晋江 |
| |
| 作者单位： | 郑州大学数学系 |
| |
| 摘 要： | 本文证明了既使对３－正则３－连通无爪平面图，Ｈａｍｉｌｔｏｎ圈（路）问题也是ＮＰ－完全的．
|
| 关 键 词： | 路，圈，无爪，NP－完全 |
NP-Completeness of Hamilton Circuit Problem and Hamilton Path Problem for 3-Regular 3-Connected Claw-Free Planar Graphs |
| |
| Yuan Jinjiang.NP-Completeness of Hamilton Circuit Problem and Hamilton Path Problem for 3-Regular 3-Connected Claw-Free Planar Graphs[J].Journal of Xinjiang University(Science & Engineering),1994(3). |
| |
| Authors: | Yuan Jinjiang |
| |
| Abstract: | This paper shows that Hamilton circuit (path) problem is NP-complete even for 3-regular 3-connected claw-free planar graphs. |
| |
| Keywords: | Path Circuit Claw-free NP-complete |
| 本文献已被 CNKI 等数据库收录！ |
