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

DOI10.1016/j.disopt.2006.06.002zbMath1112.90012MaRDI QIDQ865758

Bao Nguyen Nguyen, Hoong Chuin Lau, Trung Hieu Ngo

Publication date: 20 February 2007

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://ink.library.smu.edu.sg/sis_research/1188

zbMATH Keywords

algorithm; computational complexity; network design; logistics

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B06: Transportation, logistics and supply chain management

90B10: Deterministic network models in operations research

Related Items

Exact and Approximation Algorithms for the Expanding Search Problem, The density maximization problem in graphs, Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths, An improved algorithm for finding a length-constrained maximum-density subtree in a tree, An optimal algorithm for the maximum-density path in a tree, Attack and defense in the layered cyber-security model and their \((1 \pm \varepsilon)\)-approximation schemes, Enumeration of subtrees and BC-subtrees with maximum degree no more than \(k\) in trees

Cites Work

• Unnamed Item
• An efficient algorithm for the length-constrained heaviest path problem on a tree
• Linear-time algorithm for finding a maximum-density segment of a sequence
• Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications
• Finding a length-constrained maximum-density path in a tree
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• An Optimal Algorithm for the Maximum-Density Segment Problem