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

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

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)

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 (2)

• Extensive facility location problems on networks: an updated review
• An efficient algorithm for the length-constrained heaviest path problem on a 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)