| Minimum Global Height支撑树及相关问题 |
| |
| 引用本文： | 李帮义,盛昭瀚. Minimum Global Height支撑树及相关问题[J]. 系统科学与数学, 2002, 22(4): 422-427 |
| |
| 作者姓名： | 李帮义 盛昭瀚 |
| |
| 作者单位： | 南京大学管理科学与工程研究院,南京,210016 |
| |
| 基金项目： | 国家自然科学基金（70171028），航空基金（S0133-092）资助课题 |
| |
| 摘 要： | 本文研究了两个组合优化问题:minimum g1obal height支撑树和minimum aveageheight支撑树问题.利用3SAT问题的时间复杂性,本文证明了这两个问题都是NP-hard的,并分别给出了一个算法,即（mgh）-算法和（mah）-算法.在非负网络中,这两个算法的时间复杂性都为O（n3）.利用第一个问题的复杂性,本文证明了minimum height支撑树问题也是NP-hard的,从而纠正了有关文献中的一个错误结论.
|
| 关 键 词： | 支撑树 算法 NP-hard |
| 修稿时间： | 2000-04-04 |
THE MINIMUM GLOBAL HEIGHT SPANNING TREE AND RELATED PROBLEMS |
| |
| Bang Yi LI,Zhao Han SHENG. THE MINIMUM GLOBAL HEIGHT SPANNING TREE AND RELATED PROBLEMS[J]. Journal of Systems Science and Mathematical Sciences, 2002, 22(4): 422-427 |
| |
| Authors: | Bang Yi LI Zhao Han SHENG |
| |
| Affiliation: | Graduate School of Management Science and Engineering, Nanjing University, Nanjing 210093,P.R.China |
| |
| Abstract: | Two optimization problems are concerned in this paper(i.e.): the minimum global height spanning tree problem and the minimum average height spanning tree problem. Using the time complexity status of 3SAT problem, the two problems are proven to be NP-hard and two algorithms are to be designed for the problems. In nonnegative networks, the time complexity of the two algorithms are all O(n3). Using the complexity status of the first problem, we prove that the minimum height spanning tree problem is NP-hard, so the paper revises an error result given by one of the references. |
| |
| Keywords: | Spanning tree algorithm NP-hard. |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 |
|
点击此处可从《系统科学与数学》下载全文 |
|
