Regular sparse crossbar concentrators

A bipartite concentrator is a single stage sparse crossbar switching device that can connect any m of its n greater than or equal to m inputs to its m outputs, possibly without the ability to distinguish their order. Fat-and-slim crossbars were introduced recently to show that bipartite concentrators can be constructed with a minimum number of crosspoints for any number of inputs and outputs. We generalize these graphs to obtain bipartite concentrators with nearly a fixed fanout without altering their (n - m + 1)m crosspoint complexity. We also present an O(log n)-time algorithm to route arbitrary concentration assignments on this new family of fat-and-slim crossbars.