Edge Ranking (ER)

Input

A tree $T = (V, E)$.

Problem

Find an optimal edge ranking of $T$.

Definitions

An edge ranking of a tree is a labeling of the edges using positive integers such that the path between two edges with the same label contains an intermediate edge with a higher label. An edge ranking is optimal if the highest label used is as small as possible.

Status

Open (Dessmark, Lingas, and Maheshwari [1]).

Remarks

This problem was proved to be in $\P$ in [2]. They give a $\NC$ approximation algorithm for the problem that finds an edge ranking within a factor of two of optimal. An $\NC$ algorithm for constant degree trees is also given in [2]. A similar problem called the Node Ranking Problem for trees in which the vertices are labeled, instead of the edges, was proved to be in $\NC$ (de la Torre and Greenlaw [3], de la Torre, Greenlaw, and Przytycka [4]). See FILL for a related $\P$-complete problem. Karloff and Shmoys give $\NC$ algorithms for several versions of edge ranking multigraphs [5], a problem having a similar flavor. See LFDVC and EC for a description of their results.