| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 421028 | Discrete Applied Mathematics | 2006 | 12 Pages |
Abstract
In this paper we consider the edge ranking problem of weighted trees. We prove that a special instance of this problem, namely edge ranking of multitrees is NP-hard already for multitrees with diameter at most 10. Note that the same problem but for trees is linearly solvable. We give an O(logn)O(logn)-approximation polynomial time algorithm for edge ranking of weighted trees.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dariusz Dereniowski,