Loading...
Please wait, while we are loading the content...
Similar Documents
Node-disjoint multipath spanners and their relationship with fault-tolerant spanners.
| Content Provider | CiteSeerX |
|---|---|
| Author | Gavoille, Cyril Godfroy, Quentin Viennot, Laurent |
| Abstract | Abstract. Motivated by multipath routing, we introduce a multiconnected 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 aweightedgraphG, a subgraph H is a p-multipath s-spanner if for all u, v, thep-multipath cost between u and v in H is at most s times the p-multipath cost in G. Thes 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 Õ(n1+1/k) edges 1, 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. 1 |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Fault-tolerant Spanner P-multipath Cost Node-disjoint Multipath Spanner Distributed Algorithm Minimum Weight Constant Stretch Vertex-disjoint Path P-multipath S-spanner Maximum Edge Weight Multiconnected Variant Multipath Routing Thes Factor Given Aweightedgraphg Thep-multipath Cost P-multipath Spanner Fixed Parameter Recent Result Improved Construction |
| Content Type | Text |
| Resource Type | Article |
