Degree Switching Operations in Networks and Large Scale Systems Assignment Problems

In this paper an algorithm is presented for listing all output sets for a large sparse square matrix A arising in large scale systems applications using network theory and the degree switching operations. The algorithm exploits the zero nonzero structure of matrix A and uses optimum data structures and data manipulation methods. The method is shown to be useful in finding all optimum assignments in an n x n optimum assignment problem and generation of all digraphs that can be associated with an n x nsparse matrix. The problem of testing whether there exists a set of vertex disjoint cycles of specified lengths in a network is shown to be NP-complete.