Finding a maximum-density path in a tree under the weight and length constraints

DOI10.1016/j.ipl.2007.08.031zbMath1184.68602OpenAlexW2138622863MaRDI QIDQ2380075

Chih-Sheng Cheng, Sun-Yuan Hsieh

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.08.031

zbMATH Keywords

pathsalgorithmstreesnetwork designdesign and analysis of algorithmssubgraph optimization problems

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

The density maximization problem in graphs ⋮ Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths ⋮ Invulnerability of planar two-tree networks ⋮ 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

Uses Software

• EMBOSS
• MAVG

Cites Work

• 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

This page was built for publication: Finding a maximum-density path in a tree under the weight and length constraints