Some tractable instances of interval data minmax regret problems

In this paper, we provide polynomial and pseudopolynomial algorithms for classes of particular instances of interval data minmax regret graph problems. These classes are defined using a parameter that measures the distance from well-known solvable instances. Tractable cases occur when the parameter is bounded by a constant.