Efficient algorithms and methods to solve dynamic MINs stability problem using stable matching with complete ties

AbstractWe claimed that Stable Matching problems are the same as problems about stable configurations of Multi-stage Interconnection Networks (MINs). We solved the Regular and Irregular MINs Stability Problems using the approaches and solutions provided by the Stable Matching Problem. Specifically we have used Stable Marriage Problem as an example of Stable Matching. Two algorithms are proposed:—the first algorithm generates the MINs Preferences List in O(n2) time and second algorithm produces a set of most Optimal Pairs of the Switching Elements (SEs), derived from the MINs Preferences List in O(n) time. Consequences include new algorithms for finding a Stable Matching between the SEs, an understanding of the difference between MINs Stability and Unstability problems, Algorithms used for generating the Preference Lists for the MINs, methods, and procedures used for deriving the Optimal Pairs from the MINs Preference Lists, and solving ties between them