Remarks on implementation of O ( n 1/2 τ) assignment algorithms
- 1 September 1988
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 14 (3) , 267-287
- https://doi.org/10.1145/44128.44131
Abstract
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τ ).Keywords
This publication has 8 references indexed in Scilit:
- On Algorithms for Obtaining a Maximum TransversalACM Transactions on Mathematical Software, 1981
- Algorithm 575: Permutations for a Zero-Free Diagonal [F1]ACM Transactions on Mathematical Software, 1981
- A comparasion of three resequencing algorithms for the reduction of matrix profile and wavefrontInternational Journal for Numerical Methods in Engineering, 1979
- An Automatic Nested Dissection Algorithm for Irregular Finite Element ProblemsSIAM Journal on Numerical Analysis, 1978
- A survey of sparse matrix researchProceedings of the IEEE, 1977
- FINDING THE BLOCK LOWER TRIANGULAR FORM OF A SPARSE MATRIXPublished by Elsevier ,1976
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973
- An Algorithm for Distinct RepresentativesThe American Mathematical Monthly, 1956