【摘要】 针对进化树中的限长最大密集度路径的求解问题提出一种更优的算法。该算法能以伪多项式时间O(wmaxnL)在节点数目为n,且每个节点携带值-权重向量(βv,γv)的进化树中找到一条长度至少为L的路径P,其密集度为最大且满足wmin≤∑v∈Pγv≤wmax.更多还原

【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).更多还原