Optimal Algorithms for Finding Density-Constrained Longest and Heaviest Paths in a Tree

Sung Kwon KIM  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.11   pp.2989-2994
Publication Date: 2010/11/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.2989
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
algorithms,  density-constrained paths,  heaviest paths,  longest paths,  

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



Summary: 
Let T be a tree with n nodes, in which each edge is associated with a length and a weight. The density-constrained longest (heaviest) path problem is to find a path of T with maximum path length (weight) whose path density is bounded by an upper bound and a lower bound. The path density is the path weight divided by the path length. We show that both problems can be solved in optimal O(n log n) time.