DIMACS TR: 2003-27
Minimum Edge Ranking Spanning Trees of Split Graphs
Authors: Kazuhisa Makino, Yushi Uno, Toshihide Ibaraki
ABSTRACT
Given a graph $G$,
the minimum edge ranking spanning tree problem (MERST)
is to find a spanning tree of $G$ whose edge ranking is minimum.
However, 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 split 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.
We also show that the problem MERST for threshold graphs can be solved
in linear time, where threshold graphs are known to be split.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-27.ps.gz
DIMACS Home Page