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.
Algorithm for the Length-Constrained Maximum-Density Path Problem in a Tree with Uniform Edge Lengths
Sung Kwon KIM
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/01/01
Online ISSN: 1745-1361
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
length-constrained paths, maximum-density paths, uniform edge lengths,
Full Text: PDF(323.8KB)>>
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.