The Maximum Partition Matching Problem with Applications

Let ${\cal S} = {C 1 , C 2 , . . . , C k }$ be a collection of pairwise disjoint subsets of U = { 1, 2, . . . , n} such that $\bigcup_{i = 1}^k C i = U. A partition matching of $\cal S$ consists of two subsets {a 1 , . . . , a m } and {b 1 , . . ., b m } of U together with a sequence of distinct partitions of $\cal S$: $({\cal A}_1, {\cal B}_1), \ldots, ({\cal A}_m, {\cal B}_m)$ such that a i is contained in a subset in the collection ${\cal A}_i$ and b i is contained in a subset in the collection ${\cal B}_i$ for all i = 1, . . . , m. An efficient algorithm is developed that constructs a maximum partition matching for a given collection $\cal S$. The algorithm can be used to construct optimal parallel routing between two nodes in interconnection networks.