Survivable Networks with Bounded Delay: The Edge Failure Case

We introduce new classes of graphs to investigate networks that guarantee constant delays even in the case of multiple edge failures. This means the following: as long as two vertices remain connected if some edges have failed, then the distance between these vertices in the faulty graph is at most a constant factor k times the original distance. In this extended abstract, we consider the case where the number of edge failures is bounded by a constant l. These graphs are called (k, l)–self-spanners. We prove that the problem of maximizing l for a given graph when k > 4 is fixed is NP-complete, whereas the dual problem of minimizing k when l is fixed is solvable in polynomial time. We show how the Cartesian product affects the self-spanner properties of the composed graph. As a consequence, several popular network topologies (like grids, tori, hypercubes, butterflies, and cube-connected cycles) are investigated with respect to their self-spanner properties.