Finding a length-constrained maximum-density path in a tree

DOI10.1007/S10878-005-6853-7MaRDI QIDQ1781798zbMATH OpenOpenAlexFDO

Authors Rung-Ren Lin, Wen-Hsiung Kuo, Kun-Mao Chao

Publication date 8 June 2005

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-005-6853-7

zbMATH Keywords

treealgorithmcomputational biologynetwork design

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Protein sequences, DNA sequences (92D20) Graph algorithms (graph-theoretic aspects) (05C85) Physiological, cellular and medical topics (92Cxx)

Recommendations

• Algorithms and Computation
• An optimal algorithm for the maximum-density path in a tree
• Algorithms and Computation
• An improved algorithm for finding a length-constrained maximum-density subtree in a tree
• Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths
• An efficient algorithm for the length-constrained heaviest path problem on a tree
• Finding a longest nonnegative path in a constant degree tree
• Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics
• Maximal path length of binary trees
• A pathfinding problem for search trees with unknown edge length

Cites work

• scientific article; zbMATH DE number 1945161 (Why is no real title available?)
• An efficient algorithm for the length-constrained heaviest path problem on a tree
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• Linear-time algorithm for finding a maximum-density segment of a sequence
• On computing all suboptimal alignments

Cited in

(13)

• A pathfinding problem for search trees with unknown edge length
• Algorithms and Computation
• Algorithms and Computation
• Finding a longest nonnegative path in a constant degree tree
• scientific article; zbMATH DE number 3977047 (Why is no real title available?)
• An improved algorithm for finding a length-constrained maximum-density subtree in a tree
• Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence
• Finding a maximum-density path in a tree under the weight and length constraints
• Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees
• An optimal algorithm for the maximum-density path in a tree
• An efficient algorithm for the length-constrained heaviest path problem on a tree
• Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics
• Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths

Describes a project that uses

Uses Software

• MAVG

This page was built for publication: Finding a length-constrained maximum-density path in a tree

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