
For FullText 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.

Optimal Algorithms for Finding the Longest Path with Length and Sum Constraints in a Tree
Sung Kwon KIM
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E94D
No.6
pp.13251328 Publication Date: 2011/06/01 Online ISSN: 17451361
DOI: 10.1587/transinf.E94.D.1325 Print ISSN: 09168532 Type of Manuscript: LETTER Category: Fundamentals of Information Systems Keyword: length constraint, longest path, sum constraint, tree,
Full Text: PDF(84.9KB)>>
Summary:
Let T be a tree in which every edge is associated with a real number. The sum of a path in T is the sum of the numbers associated with the edges of the path and its length is the number of the edges in it. For two positive integers L_{1} ≤ L_{2} and two real numbers S_{1} ≤ S_{2}, a path is feasible if its length is between L_{1} and L_{2} and its sum is between S_{1} and S_{2}. We address the problem: Given a tree T, and four numbers, L_{1}, L_{2}, S_{1} and S_{2}, find the longest feasible path of T. We provide an optimal O(n log n) time algorithm for the problem, where n =T.

