Pendants-median支撑树及其一个相关问题:复杂性和算法  

PENDANTS-MEDIAN SPANNING TREE PROBLEM AND ONE RELATED PROBLEM: COMPLEXITY AND ALGORITHM

作　　者：付铅生[1] 李帮义[1] 

机构地区：[1]南京航空航天大学经济管理学院工商管理系,南京210016

出　　处：《高等学校计算数学学报》2004年第2期132-138,共7页Numerical Mathematics A Journal of Chinese Universities

基　　金：江苏省教育厅人文社科基金(02S5D630020)

摘　　要：1引言 最小支撑树问题是个经典的组合优化问题,该问题已有很长的研究历史(见[1]),并已很好地解决了,如Dijkstra算法、Kruskal算法、Prim算法等.但随着信息科学和决策科学的发展,最小支撑树问题又出现了一些新的变形问题,如[2]中就研究了目标函数依赖于树叶的支撑树问题.The complexity status of Pendants-median spanning tree problem is an open problem. Using the complexity of the X3C problem, the paper proves that Pendants-median spanning tree problem is NP-complete. Global-median spanning tree problem is a related problem. Using the complexity of 3SAT, the paper proves that this problem is also NP-complete, and a polynomial -time algorithm to this problem is given, whose time complexity is O(n3).

关 键 词：支撑树 集合 NP-完全 最短路树 树叶 

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