An improved algorithm for finding a length-constrained maximum-density subtree in a tree |
| |
Authors: | Hsin-Hao Su Chuan Yi Tang |
| |
Affiliation: | a Department of Computer Science, National Tsing Hua University, Hsinchu 300, Taiwan b Institute of Bioinformatics, National Chiao Tung University, Hsinchu 300, Taiwan c Department of Biological Science and Technology, National Chiao Tung University, Hsinchu 300, Taiwan |
| |
Abstract: | Given a tree T with weight and length on each edge, as well as a lower bound L and an upper bound U, the so-called length-constrained maximum-density subtree problem is to find a maximum-density subtree in T such that the length of this subtree is between L and U. In this study, we present an algorithm that runs in O(nUlogn) time for the case when the edge lengths are positive integers, where n is the number of nodes in T, which is an improvement over the previous algorithms when U=Ω(logn). In addition, we show that the time complexity of our algorithm can be reduced to , when the edge lengths being considered are uniform. |
| |
Keywords: | Algorithms Dynamic programming Trees Network design Divide and conquer |
本文献已被 ScienceDirect 等数据库收录! |
|