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

DOI10.1016/J.IPL.2008.05.023MaRDI QIDQ975474zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

algorithmsanalysis of algorithmsdata structures

Mathematics Subject Classification ID

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

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

Cites work

• An \(O(n)\) algorithm for finding an optimal position with relative distances in an evolutionary tree
• An O(pn^ 2) algorithm for the p-median and related problems on tree graphs
• An efficient algorithm for the length-constrained heaviest path problem on a tree
• 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)