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.
Optimal Algorithms for Finding Density-Constrained Longest and Heaviest Paths in a Tree
Sung Kwon KIM
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2010/11/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
algorithms, density-constrained paths, heaviest paths, longest paths,
Full Text: PDF(202.7KB)>>
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.