The operating schedule problem in open-pit mine can be associated with the problem of maximal closure on a graph. In the literature, the Lagrangian relaxation represents the most interesting approach to solve this problem. The problem resulting from the relaxation of the resource constraints is a sequence of ultimate pit contour (UPC) problems, which ones are solved using a maximal flow algorithm. This paper focuses on the solution of the UCP problem and proposes an analysis of different maximal flow algorithms to solve this problem, taking into account the structure of the graph that are involved. Some accelerating strategies are described and analyzed.