Finding a longest nonnegative path in a constant degree tree

DOI10.1016/J.IPL.2004.11.012MaRDI QIDQ835050zbMATH OpenOpenAlexFDO

Authors Sung Kwon Kim

Publication date 27 August 2009

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

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

zbMATH Keywords

algorithmstreesnonnegative paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Finding a length-constrained maximum-density path in a tree
• Algorithms and Computation
• An efficient algorithm for the length-constrained heaviest path problem on 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
• Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees

Cites work

• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An efficient algorithm for the length-constrained heaviest path problem on a tree

Cited in

(5)

• Algorithms and Computation
• 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 length-constrained maximum-density path in a tree
• Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees
• Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths

Describes a project that uses

Uses Software

• SEGID

This page was built for publication: Finding a longest nonnegative path in a constant degree tree

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