| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10331423 | Information Processing Letters | 2005 | 5 Pages |
Abstract
A longest nonnegative path in an edge-weighted tree is a path such that the sum of edge weights on it is nonnegative and the number of edges on it is as large as possible. In this paper we show that if a tree has a constant degree, then its longest nonnegative path can be found in O(nlogn) time, where n is the number of nodes. Previously known algorithms take O(nlog2n) time.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sung Kwon Kim,