Algorithm for the Length-Constrained Maximum-Density Path Problem in a Tree with Uniform Edge Lengths

Sung Kwon KIM  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.1   pp.103-107
Publication Date: 2015/01/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014EDP7009
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
length-constrained paths,  maximum-density paths,  uniform edge lengths,  

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




Summary: 
Given an edge-weighted tree with n vertices and a positive integer L, the length-constrained maximum-density path problem is to find a path of length at least L with maximum density in the tree. The density of a path is the sum of the weights of the edges in the path divided by the number of edges in the path. We present an O(n) time algorithm for the problem. The previously known algorithms run in O(nL) or O(n log n) time.