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 L1L2 and two real numbers S1S2, 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|.