河南科学
河南科學
하남과학
HENAN SCIENCE
2006年
5期
715-718
,共4页
算法复杂性%NP-完全性%团
算法複雜性%NP-完全性%糰
산법복잡성%NP-완전성%단
对最大团问题的HEWN(hierarchical edge-weight network)算法进行了复杂性分析.首先通过分析HEWN的结构特点和所需进行的操作,设计了一种实现HEWN算法的数据结构,指出了在HEWN算法中HEWN的存储宜采用邻接多重表和二叉链表相结合的链表表示法,然后从HEWN的存储结构入手,剖析了HEWN的构造过程,在剖析过程中,通过与MCST(maximum complete sub-graph tree)比较,指出了当2j＞n时潜在的、指教的生成和修改GM的次数存在于HEWN算法中.因而,HEWN算法的时间复杂度是指数的,而不是O(n85).
對最大糰問題的HEWN(hierarchical edge-weight network)算法進行瞭複雜性分析.首先通過分析HEWN的結構特點和所需進行的操作,設計瞭一種實現HEWN算法的數據結構,指齣瞭在HEWN算法中HEWN的存儲宜採用鄰接多重錶和二扠鏈錶相結閤的鏈錶錶示法,然後從HEWN的存儲結構入手,剖析瞭HEWN的構造過程,在剖析過程中,通過與MCST(maximum complete sub-graph tree)比較,指齣瞭噹2j＞n時潛在的、指教的生成和脩改GM的次數存在于HEWN算法中.因而,HEWN算法的時間複雜度是指數的,而不是O(n85).
대최대단문제적HEWN(hierarchical edge-weight network)산법진행료복잡성분석.수선통과분석HEWN적결구특점화소수진행적조작,설계료일충실현HEWN산법적수거결구,지출료재HEWN산법중HEWN적존저의채용린접다중표화이차련표상결합적련표표시법,연후종HEWN적존저결구입수,부석료HEWN적구조과정,재부석과정중,통과여MCST(maximum complete sub-graph tree)비교,지출료당2j＞n시잠재적、지교적생성화수개GM적차수존재우HEWN산법중.인이,HEWN산법적시간복잡도시지수적,이불시O(n85).
