Quest for Good Spanners of Hypercubes

The quest for good spanners of hypercubes is motivated by their usage as network architectures. Spanners that keep short distances while reducing size or that offer multiple edge-disjoint paths between nodes are favoured. In particular, a 3-spanner guarantees that neighbours in the original graph remain within distance 3 in the spanner. There are known constructions of sparse 3-spanners of hypercubes but they are inefficient for small dimensions. We show two constructions efficient for small dimensions, which improve previously known upper bound on the minimal size of hypercube 3-spanners. We present a genetic algorithm with new hypercube-specific operators and fitness functions addressing the problems of finding a 3-spanner of minimal size and finding multiple edge-disjoint spanners. We evaluate it over a variety of settings and emphasize the most notable ones. For small dimensions the computed results match the new improved constructions this paper presents and for higher dimensions they exceed previously known results.