Minimum edge ranking spanning trees of threshold graphs

摘要

The minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of a given G whose edge ranking is minimum. This problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for threshold graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable.