FROM HALL MATCHING THEOREM TO OPTIMAL ROUTING ON HYPERCUBES

We introduce a concept of so-called disjoint ordering for any collecti on of finite sets. It can be viewed as a generalization of a system of distinctive representatives for the sets. It is shown that disjoint o rdering is useful for network routing. More precisely, we show that Ha ll's ''marriage'' condition for a collection of finite sets guarantees the existence of a disjoint ordering for the sets. We next use this r esult to solve a problem in optimal routing on hypercubes. We give a n ecessary and sufficient condition under which there are internally nod e-disjoint paths each shortest from a source node to any other s (s le ss than or equal to n) target nodes on an n-dimensional hypercube. Whe n this condition is not necessarily met, we show that there are always internally node-disjoint paths each being either shortest or near sho rtest, and the total length is minimum. An efficient algorithm is also given for constructing disjoint orderings and thus disjoint short pat hs. As a consequence, Rabin's information disposal algorithm may be im proved. (C) 1998 Academic Press.