2011/09/13 by Cyril Gavoille, Gavoille, Cyril, Quentin Godfroy +3
Computer Science · Engineering · #Advanced Optical Network Technologies #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems #Networking and Internet Architecture (cs.NI) #cs.DM #cs.NI
paper · pdf · doi:10.48550/arxiv.1109.2696
openalex publication_date 2011/09/13 · arxiv created 2011/09/16 · arxiv updated 2011/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 minimum weight of a collection of p internally vertex-disjoint paths between u and v. Given a weighted graph G, a subgraph H is a p-multipath s-spanner if for all u,v, the p-multipath cost between u and v in H is at most s times the p-multipath cost in G. The s factor is called the stretch. Building upon recent results on fault-tolerant spanners, we show how to build p-multipath spanners of constant stretch and of \tO(n1+1/k) edges, for fixed parameters p and k, n being the number of nodes of the graph. Such spanners can be constructed by a distributed algorithm running in O(k) rounds. Additionally, we give an improved construction for the case p=k=2. Our spanner H has O(n3/2) edges and the p-multipath cost in H between any two node is at most twice the corresponding one in G plus O(W), W being the maximum edge weight.