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

DOI10.1016/j.ipl.2008.05.023zbMath1191.68202OpenAlexW2040381019MaRDI QIDQ975474

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)

Related Items (1)

Extensive facility location problems on networks: an updated review

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
• Finding a longest nonnegative path in a constant degree tree
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• Mathematical Foundations of Computer Science 2003

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