Algorithm for finding a Length-constrained heaviest path of a tree


The KIPS Transactions:PartA, Vol. 13, No. 6, pp. 541-544, Dec. 2006
10.3745/KIPSTA.2006.13.6.541,   PDF Download:

Abstract

Abstract: In a tree with each edge associated with a length and a weight (positive, negative, or zero are possible) we develop an O(nlogn log logn) time algorithm for finding a path such that its sum of weights is maximized and its sum of lengths does not exceed a given value. The previously best-known result is O(nlog²n), where n is the number of nodes in the tree.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
S. K. Kim, "Algorithm for finding a Length-constrained heaviest path of a tree," The KIPS Transactions:PartA, vol. 13, no. 6, pp. 541-544, 2006. DOI: 10.3745/KIPSTA.2006.13.6.541.

[ACM Style]
Sung Kwon Kim. 2006. Algorithm for finding a Length-constrained heaviest path of a tree. The KIPS Transactions:PartA, 13, 6, (2006), 541-544. DOI: 10.3745/KIPSTA.2006.13.6.541.