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

DOI10.1016/J.IPL.2007.08.031MaRDI QIDQ2380075zbMATH OpenOpenAlexFDO

Authors Sun-Yuan Hsieh, Chih-Sheng Cheng

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

algorithmsdesign and analysis of algorithmsnetwork designpathssubgraph optimization problemstrees

Mathematics Subject Classification ID

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

Cites work

• An efficient algorithm for the length-constrained heaviest path problem on a tree
• An Optimal Algorithm for the Maximum-Density Segment Problem
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• Finding a length-constrained maximum-density path in 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

Cited in

(5)

• Invulnerability of planar two-tree networks
• 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

Describes a project that uses

Uses Software

• EMBOSS
• MAVG

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380075)