For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2013/03/01
Online ISSN: 1745-1361
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)>>
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.