AN efficient method for the representation and transmission of message patterns
Philip J. Bernhard, Daniel J. Rosenkrantz · 2003
A formalism is described for the compact representation of message patterns for multistage interconnection networks. In this formalism a descriptor called an (s,d)-mask is used to represent a message pattern, or rather, a set of messages. It is shown that when message patterns are represented in this way a number of their properties can be determined in polynomial time. This includes determining if a message pattern creates conflicts or congestion. In addition, it is shown that the minimum round partitioning problem, which in general is NP-complete, can be solved in polynomial time for any message pattern which can be represented by a single (s,d)-mask. The generalizes a known result to a more general class of message patterns and a more general class of networks.>