A classification of minimal standard-path 2 × 2 switching networks

AbstractWe consider n-inlet, n-outlet networks of 2 × 2 switches with the property that, given inlet—outlet pair, there is a standard path between them which is always free to be as a connection path provided the inlet and outlet are free. We show that the minimum number of 2 × 2 switches for such a network is n2−⌊ 3n/2 ⌋. The minimal network has a novel spiral structure. If the network is staged, this minimum rises to n2−2⌊ n/2 ⌋ −1, while if the network is staged and planar, it rises to n2−⌊ n/2 ⌋−2 or n2−⌊ n/2 ⌋−1. Furthermore, designing of minimal staged networks is shown to be essentially equivalent to finding an optimal strategy for a certain solitaire game played with matches. For staged planar networks, there is a corresponding coin game