Algorithm for finding a Length-constrained heaviest path of a tree 


Vol. 13,  No. 6, pp. 541-544, Dec.  2006
10.3745/KIPSTA.2006.13.6.541


PDF
  Abstract

Abstract: In a tree with each edge associated with a length and a weight (positive, negative, or zero are possible) we develop an O(nlogn log logn) time algorithm for finding a path such that its sum of weights is maximized and its sum of lengths does not exceed a given value. The previously best-known result is O(nlog²n), where n is the number of nodes in the tree.

  Statistics
  Cite this article

[IEEE Style]

S. K. Kim, "Algorithm for finding a Length-constrained heaviest path of a tree," The KIPS Transactions:PartA, vol. 13, no. 6, pp. 541-544, 2006. DOI: 10.3745/KIPSTA.2006.13.6.541.

[ACM Style]

Sung Kwon Kim. 2006. Algorithm for finding a Length-constrained heaviest path of a tree. The KIPS Transactions:PartA, 13, 6, (2006), 541-544. DOI: 10.3745/KIPSTA.2006.13.6.541.

Forms

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)

Old Journals

Indexing

All publications of TKIPS is indexed in DOI, EBSCO, Google Scholar, Crossref, and CrossCheck.

TKIPS is also selected as the Journal for Accreditation by NRF (National Research Foundation of Korea).

Related Journals