Node-Disjoint Multipath Spanners and Their Relationship with Fault-Tolerant Spanners
Node-Disjoint Multipath Spanners and Their Relationship with Fault-Tolerant Spanners
复制标题
节点不相交的多路径 Spanner 及其与容错 Spanner 的关系
DOI：
10.1007/978-3-642-25873-2_11
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
L. Viennot
中科院分区：
文献类型：
--
作者：
C. Gavoille;Quentin Godfroy;L. Viennot
由多路由路由的激励，我们引入了多个跨度的多种连接变体。为此，我们将两个节点u和V之间的p-multipath成本引入了u和v。u和v。的p内部顶点 - 偶发路径的最小重量，给定加权图G，一个子图H是p-multipath s -Spanner如果对于所有U，V，H中u和V之间的p-multipath成本最多是g中的p-multipath成本。S因子称为拉伸。
在最新的耐故障跨度的结果基础上，我们展示了如何构建不变拉伸的p-multipath跨度和$ {\ tilde {o}}}}（n^{1+1/k}）$ edges，用于固定参数p k，n是图的节点的数量。可以通过在O（k）回合中运行的分布式算法来构建此类跨度。
此外，我们为Case P = K = 2提供了改进的结构。我们的SPANNER H具有O（N3/2）边缘，并且在任何两个节点之间的H中的P-Multipath成本最多是G plus O（w）中相应的两个节点的两倍，W是最大边缘重量。
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 ${\tilde{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(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.