摘要：An edge-ranking of a graph G is a labeling of the edges of G with positive integers such that
every path between two edges with the same label ¡ã contains an edge with label . > ¡ã. In the on-line
edge-ranking model the edges e1; e2 : : : ; em arrive one at a time in any order, where m is the number of
edges in the graph. Only the partial information in the induced subgraph G[fe1; e2; : : : ; eig] is available
when the algorithm must choose a rank for ei. In this paper, we present an on-line algorithm for ranking
the edges of a tree in time O(n2), where n is the number of vertices in the tree.
