Paper Info
Title
An improved algorithm for finding a length-constrained maximum-density subtree in a tree
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=@W(logn). In addition, we show that the time complexity of our algorithm can be reduced to O(nLlognL), when the edge lengths being considered are uniform.
Year
DOI
Venue
2008
10.1016/j.ipl.2008.09.027
Inf. Process. Lett.
Keywords
Field
DocType
maximum-density subtree,positive integer,upper bound u,so-called length-constrained maximum-density subtree,edge length,improved algorithm,previous algorithm,time complexity,lower bound l,control theory,algorithms,lower bound,upper bound,dynamic programming,systems engineering,divide and conquer,network design
Integer,Dynamic programming,Discrete mathematics,Combinatorics,Algorithm complexity,Upper and lower bounds,Tree (data structure),Algorithm,Divide and conquer algorithms,Time complexity,Mathematics,Maximum density
Journal
Volume
Issue
ISSN
109
2
0020-0190
Citations 
PageRank 
References 
5
0.49
11
Authors
3
Name
Order
Citations
PageRank
Hsin-Hao Su1949.38
Chin Lung Lu242334.59
Chuan Yi Tang370479.25