Node-Disjoint Multipath Spanners and their Relationship with Fault-Tolerant Spanners

Cyril Gavoille, Quentin Godfroy, Laurent Viennot

Motivated by multipath routing, we introduce a multi-connected variant of spanners. For that purpose we introduce the $p$-multipath cost between two nodes $u$ and $v$ as the minimu…