Publication Type

Journal Article

Publication Date

12-2006

Abstract

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.

Keywords

Network design, Algorithm, Computational complexity, Logistics

Discipline

Numerical Analysis and Scientific Computing | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Decision Analytics

Publication

Discrete Optimization

Volume

3

Issue

4

First Page

385

Last Page

391

ISSN

1572-5286

Identifier

10.1016/j.disopt.2006.06.002

Publisher

Elsevier

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

http://doi.org/10.1016/j.disopt.2006.06.002