Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees

DOI10.1016/J.IPL.2008.05.023zbMATH Open1191.68202OpenAlexW2040381019MaRDI QIDQ975474FDOQ975474

Authors: Bishnu Bhattacharyya, Frank Dehne 

Publication date: 9 June 2010

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

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

Recommendations

• An efficient algorithm for the length-constrained heaviest path problem on a tree
• Algorithms and Computation
• Finding a length-constrained maximum-density path 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
• An improved algorithm for finding a length-constrained maximum-density subtree in a tree

zbMATH Keywords

algorithmsanalysis of algorithmsdata structures

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05)

Cites Work

• An \(O(n)\) algorithm for finding an optimal position with relative distances in an evolutionary tree
• An efficient algorithm for the length-constrained heaviest path problem on a tree
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• Finding a longest nonnegative path in a constant degree tree
• Mathematical Foundations of Computer Science 2003
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time

Cited In (3)

• Extensive facility location problems on networks: an updated review
• An efficient algorithm for the length-constrained heaviest path problem on a tree
• Finding a longest nonnegative path in a constant degree tree

This page was built for publication: Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees

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