Linear-Time Algorithm for the Length-Constrained Heaviest Path Problem in a Tree with Uniform Edge Lengths

Sung Kwon KIM  

IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.3   pp.498-501
Publication Date: 2013/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.498
Print ISSN: 0916-8532
Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
length-constrained paths,  heaviest paths,  uniform edge lengths,  

Full Text: PDF(76.6KB)>>
Buy this Article

Given a tree T with edge lengths and edge weights, and a value B, the length-constrained heaviest path problem is to find a path in T with maximum path weight whose path length is at most B. We present a linear time algorithm for the problem when the edge lengths are uniform, i.e., all one. This algorithm with slight modification can be used to find the heaviest path of length exactly B in T in linear time.