List of Selected Number of Optimal Solutions of the Assignment Problem by Time Criterion

In this paper we present a solution of the assignment problem with an algorithm with complexity $O\left({{n^{\frac{9}{2}}}}\right)$. The discussed algorithm allows an effective approach for generation of a list of selected number of optimal solutions of this problem. If it is predefined that the list does not contain more than n
0
number of optimal solutions, then the proposed algorithm has complexity $\tilde nO\left({{n^{\frac{9}{2}}}}\right)$, where $\tilde n = \min \left\{ {{n_0},{n_1}} \right\}$ with n
1
being the number of perfect matchings in the graph. The method is based on the Hopcroft-Karp algorithm for maximum matching in a bipartite graphs [16].