The Maximum Partition Matching Problem with Applications Academic Article uri icon


  • Let S = {C1,C2,...,Ck} be a collection of pairwise disjoint subsets of U = {1,2,...,n} such that ∪i=1k Ci = U. A partition matching of S consists of two subsets {a1,...,am} and {b1,...,bm} of U together with a sequence of distinct partitions of S: (A1,B1),...,(Am,Bm) such that ai is contained in a subset in the collection Ai and bi is contained in a subset in the collection Bi for all i = 1,...,m. An efficient algorithm is developed that constructs a maximum partition matching for a given collection S. The algorithm can be used to construct optimal parallel routing between two nodes in interconnection networks. © 1999 Society for Industrial and Applied Mathematics.

author list (cited authors)

  • Chen, C., & Chen, J.

citation count

  • 4

publication date

  • January 1998