Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics

We study the problem of finding a length-constrained maximum-density path in a tree with weight and length on each edge. This problem was proposed in [R.R. Lin, W.H. Kuo, K.M. Chao, Finding a length-constrained maximum-density path in a tree, Journal of Combinatorial Optimization 9 (2005) 147–156] a...

Full description

Saved in:
Bibliographic Details
Main Authors: LAU, Hoong Chuin, NGO, Trung Hieu, Nguyen, Bao Nguyen
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2006
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/1188
https://ink.library.smu.edu.sg/context/sis_research/article/2187/viewcontent/Finding_a_length_constrained_maximum_sum_2006_afv.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary:We study the problem of finding a length-constrained maximum-density path in a tree with weight and length on each edge. This problem was proposed in [R.R. Lin, W.H. Kuo, K.M. Chao, Finding a length-constrained maximum-density path in a tree, Journal of Combinatorial Optimization 9 (2005) 147–156] and solved in O(nU) time when the edge lengths are positive integers, where n is the number of nodes in the tree and U is the length upper bound of the path. We present an algorithm that runs in O(nlog2n) time for the generalized case when the edge lengths are positive real numbers, which indicates an improvement when U=Ω(log2n). The complexity is reduced to O(nlogn) when edge lengths are uniform. In addition, we study the generalized problems of finding a length-constrained maximum-sum or maximum-density subtree in a given tree or graph, providing algorithmic and complexity results.