科研之友
微信
新浪微博
Facebook
分享链接
摘要
Given an edge-weighted tree with n vertices and a positive integer L, the length-constrained maximum-density path problem is to find a path of length at least L with maximum density in the tree. The density of a path is the sum of the weights of the edges in the path divided by the number of edges in the path. We present an O(n) time algorithm for the problem. The previously known algorithms run in O(nL) or O(n log n) time.
- 出版日期2015-1
