Answers are grounded in this paper and cite their sources.
Many important properties of switching networks can be effectively studied in the more general context of graph theory. In particular, the various rearrangeability properties of a network fall into this category. If G is a graph with vertex set V = I ∪ Ω, we say G is rearrangeable if, for all choices of distinct vertices, i1, i2, …, i1in I and j1, j2, …, j1in Ω, there exist vertex disjoint paths between ikand jkfor all k. In this paper, we determine the minimum number of edges any rearrangeable graph may have for all choices of I and Ω. We also discuss generalizations in which V is strictly greater than I ∪ Ω and/or t is bounded by a predetermined value. The minimal rearrangeable graphs we construct can be used to form efficient rearrangeable (and nearly rearrangeable) switching networks of arbitrary size.
No takes yet. Share an insight, caveat, or question.
Fan Chung (1975) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: