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.

published proceedings

  • SIAM Journal on Computing

author list (cited authors)

  • Chen, C., & Chen, J.

citation count

  • 4

complete list of authors

  • Chen, Chi-Chang||Chen, Jianer

publication date

  • January 1998