On Algorithms for Obtaining a Maximum Transversal

Abstract

A computer program for obtaining a permutation of a general sparse matrix that places a maxunum number of nonzero elements on its dmgonal is described. The history of this problem and the mare motivatmn for developing the algorithm are briefly chscussed Comments are made on the use of cheap heunstms, and the complexity of the algorithm is examined both in terms of its worst case bound and its performance on typmal examples. Finally, some imtml attempts at implementmg an algomthm with supermr asymptotic complexity are described.