Degree Switching Operations in Networks and Large Scale Systems Assignment Problems

✍ Scribed by Kabekode V.S. Bhat

• Publisher: Elsevier Science
• Year: 1980
• Tongue: English
• Weight: 639 KB
• Volume: 309
• Category: Article
• ISSN: 0016-0032
• DOI: 10.1016/0016-0032(80)90028-9

✦ Synopsis

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 n sparse 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.