Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #99008 (April, 1999)

On minimum edge ranking spanning trees
by Kazuhisa Makino, Yushi Uno and Toshihide Ibaraki

In this paper, we introduce the problem of computing a minimum edge ranking
spanning tree (MERST); i.e., find a spanning tree of a given graph $G$
whose edge ranking is minimum.
Although the minimum edge ranking of a given tree
can be computed in polynomial time, we show that problem MERST is NP-hard.
Furthermore, we present an approximation algorithm for MERST,
which realizes its worst case performance ratio
$\frac{\min\{(\Delta^*-1)\log n/\Delta^*,\Delta^*-1\}}{\log(\Delta^*+1)-1}$,
where $n$ is the number of vertices in $G$ and $\Delta^*$
is the maximum degree of a spanning tree whose maximum degree is minimum.
Although the approximation algorithm is a combination
of two existing algorithms for the restricted spanning tree problem
and for the minimum edge ranking problem of trees,
the analysis is based on novel properties of the edge ranking of trees.