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

DOI10.1007/978-3-642-25873-2_11MaRDI QIDQ2900968zbMATH OpenOpenAlexFDO

Authors Cyril Gavoille, Quentin Godfroy, Laurent Viennot

Publication date 27 July 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.2696

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Signed and weighted graphs (05C22) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Abstract: 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 $O(n^{1+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(n^{3/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.

Recommendations

• Multipath spanners via fault-tolerant spanners
• Fault-tolerant spanners for general graphs
• Fault tolerant spanners for general graphs
• A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners
• Edge-disjoint spanning trees on the star network with applications to fault tolerance
• Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel
• Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
• Disjoint-paths and fault-tolerant routing on recursive dual-net
• Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security

Cited in

(2)

• Multipath spanners
• Multipath spanners via fault-tolerant spanners

This page was built for publication: Node-Disjoint Multipath Spanners and Their Relationship with Fault-Tolerant Spanners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2900968)