Remarks on implementation of O ( n 1/2 τ) assignment algorithms

We examine an implementation and a number of modifications of a 1973 algorithm of Hopcroft and Karp for permuting a sparse matrix so that there are no zeros on the diagonal. We describe our implementation of the original Hopcroft and Karp algorithm and compare this with modifications which we prove to have the same O ( n 1/2 τ) behavior, where the matrix is of order n with τ entries. We compare the best of these with an efficient implementation of an algorithm whose worst-case behavior is O ( nτ ).