On an edge ranking problem of trees and graphs (Q803172)

After having introduced the concepts k-edge ranking, k-node ranking, edge rank number and node rank number, \(k\in {\mathbb{N}}\), the authors prove some of their properties, develop an O(n log n) time approximation algorithm for edge ranking of trees and conclude by mentioning that it is an open question whether one can design a polynomial-time algorithm for optimal edge ranking trees.