Edge ranking of weighted trees
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 ( log n ) -approximation polynomial time algorithm for edge ranking of weighted trees.
edge ranking approximation multigraph np-completeness polynomial algorithm