| 寻找进化树中限长最大密集度路径的一种新算法 |
| |
| 引用本文： | 葛丽芳,刘菀. 寻找进化树中限长最大密集度路径的一种新算法[J]. 贵州大学学报(自然科学版), 2010, 27(5): 60-62 |
| |
| 作者姓名： | 葛丽芳 刘菀 |
| |
| 作者单位： | 福建工程学院计算机与信息科学系,福建,福州,350108;福建工程学院计算机与信息科学系,福建,福州,350108 |
| |
| 基金项目： | 国家自然科学基金,福建省科技厅重点项目 |
| |
| 摘 要： | 针对进化树中的限长最大密集度路径的求解问题提出一种更优的算法。该算法能以伪多项式时间O(wmaxnL)在节点数目为n,且每个节点携带值-权重向量(βv,γv)的进化树中找到一条长度至少为L的路径P,其密集度为最大且满足wmin≤∑v∈Pγv≤wmax.
|
| 关 键 词： | 进化树 限长 最大密集度路径 算法 |
A Novel Algorithm for Length-constrained Maximum-concentration Path Searching in Evolutionary Tree |
| |
| GE Li-fang,LIU Yuan. A Novel Algorithm for Length-constrained Maximum-concentration Path Searching in Evolutionary Tree[J]. Journal of Guizhou University(Natural Science), 2010, 27(5): 60-62 |
| |
| Authors: | GE Li-fang LIU Yuan |
| |
| Affiliation: | an(Department of Computer and Information Science,Fujian University of Technology,Fuzhou 350108,China) |
| |
| Abstract: | This paper proposes an O（wmaxnL） algorithm that can find the length-constrained maximum-concentration path satisfying the length lower bound L and wmin≦∑v∈Pγv≦wmax,in an evolutionary tree,where the tree has n nodes such that each node v is associated with a value-weight vector（βv,γv）. |
| |
| Keywords: | evolutionary tree length-constrained maximum concentration path algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
