{"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":"2021-12-08T20:09:23","modified_gmt":"2021-12-09T01:09: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":"

Carleton University
\nTechnical Report<\/a> TR-08-06
\nApril 9, 2008<\/p>\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

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":49,"featured_media":0,"parent":12410,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"\nTR-08-06: Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-08-06 April 9, 2008 Using spine decompositions to efficiently solve the length-constrained heaviest path problem\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"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\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"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\/\",\"url\":\"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\/\",\"name\":\"TR-08-06: Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-12-09T01:08:50+00:00\",\"dateModified\":\"2021-12-09T01:09:23+00:00\",\"description\":\"Carleton University Technical Report TR-08-06 April 9, 2008 Using spine decompositions to efficiently solve the length-constrained heaviest path problem\",\"breadcrumb\":{\"@id\":\"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\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"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\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"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\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 2008\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2008\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-08-06: Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-08-06: Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees - School of Computer Science","description":"Carleton University Technical Report TR-08-06 April 9, 2008 Using spine decompositions to efficiently solve the length-constrained heaviest path problem","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"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\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"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\/","url":"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\/","name":"TR-08-06: Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-12-09T01:08:50+00:00","dateModified":"2021-12-09T01:09:23+00:00","description":"Carleton University Technical Report TR-08-06 April 9, 2008 Using spine decompositions to efficiently solve the length-constrained heaviest path problem","breadcrumb":{"@id":"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\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["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\/"]}]},{"@type":"BreadcrumbList","@id":"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\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 2008","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2008\/"},{"@type":"ListItem","position":5,"name":"TR-08-06: Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13250"}],"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\/49"}],"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"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}