Edge ranking of weighted trees

• DOI: 10.1016/j.dam.2005.11.005
• Publication Date: 2006-01-19T19:00:46Z
• Authors: Dariusz Dereniowski
• Keywords: Weight-balanced tree

AbstractIn 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)-approximation polynomial time algorithm for edge ranking of weighted trees.