Browsing by Author "Su, Hsin-Hao"

Now showing 1 - 1 of 1

An improved algorithm for finding a length-constrained maximum-density subtree in a tree
(2008-12-31)
Su, Hsin-Hao
;
Lu, Chin Lung
;
Tang, Chuan Yi
;
生物科技學系
;
生物資訊及系統生物研究所
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 (nU log n) 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 = Omega(log n). In addition, we show that the time complexity Of Our algorithm can be reduced to (nL log n/L), when the edge lengths being considered are uniform. (C) 2008 Elsevier B.V. All rights reserved.