{"id":13250,"date":"2021-12-08T20:08:50","date_gmt":"2021-12-09T01:08:50","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13250"},"modified":"2026-06-02T14:59:23","modified_gmt":"2026-06-02T18:59:23","slug":"tr-08-06-using-spine-decompositions-to-efficiently-solve-the-length-constrained-heaviest-path-problem-for-trees","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2008\/tr-08-06-using-spine-decompositions-to-efficiently-solve-the-length-constrained-heaviest-path-problem-for-trees\/","title":{"rendered":"TR-08-06: Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-08-06: Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n

Carleton University
\nTechnical Report<\/a> TR-08-06
\nApril 9, 2008<\/p>\n\n\n\n

Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
\n
\n
\n

Bishnu Bhattacharyya & Frank Dehne<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n

Abstract<\/h3>\n

The length-constrained heaviest path (LCHP) in a weighted tree T , where each edge is assigned a weight and a length, is the path P in T with maximum total path weight and total path length bounded by a given value B. This paper presents an O(n log n) time LCHP algorithm which utilizes a data structure constructed from the spine decomposition of the input tree. This is an improvement over the existing algorithm by Wu et al (1999), which runs in O(n log2 n) time. Our method also improves on a previous O(n log n) time algorithm by Kim (2005) for the special case of finding a longest nonnegative path in a constant degree tree in that we can handle trees of arbitrary degree within the same time bounds.<\/p>\n

TR-08-06.pdf<\/a><\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-08-06 April 9, 2008 Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees Bishnu Bhattacharyya & Frank Dehne Abstract The length-constrained heaviest path (LCHP) in a weighted tree T , where each edge is assigned a weight and a length, is the path P in T with […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12410,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-13250","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13250","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=13250"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13250\/revisions"}],"predecessor-version":[{"id":13251,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13250\/revisions\/13251"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12410"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13250"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13250"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}