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.E94-D   No.6   pp.1325-1328
Publication Date: 2011/06/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E94.D.1325
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
Keyword: 
length constraint,  longest path,  sum constraint,  tree,  

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



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 L1 ≤ L2 and two real numbers S1 ≤ S2, a path is feasible if its length is between L1 and L2 and its sum is between S1 and S2. We address the problem: Given a tree T, and four numbers, L1, L2, S1 and S2, find the longest feasible path of T. We provide an optimal O(n log n) time algorithm for the problem, where n =|T|.