標題: An improved algorithm for finding a length-constrained maximum-density subtree in a tree
作者: Su, Hsin-Hao
Lu, Chin Lung
Tang, Chuan Yi
生物科技學系
生物資訊及系統生物研究所
Department of Biological Science and Technology
Institude of Bioinformatics and Systems Biology
關鍵字: Algorithms;Dynamic programming;Trees;Network design;Divide and conquer
公開日期: 31-Dec-2008
摘要: 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.
URI: http://dx.doi.org/10.1016/j.ipl.2008.09.027
http://hdl.handle.net/11536/8011
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2008.09.027
期刊: INFORMATION PROCESSING LETTERS
Volume: 109
Issue: 2
起始頁: 161
結束頁: 164
Appears in Collections:Articles


Files in This Item:

  1. 000261792700016.pdf