کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421476 | 684491 | 2006 | 23 صفحه PDF | دانلود رایگان |
Given an undirected multigraph G=(V,E)G=(V,E), a family WW of sets W⊆VW⊆V of vertices (areas), and a requirement function r:Wr:W→Z+→Z+ (where Z+Z+ is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least r(W)r(W) edge-disjoint paths between vv and W for every pair of a vertex v∈Vv∈V and an area W∈WW∈W. So far this problem was shown to be NP-hard in the uniform case of r(W)=1r(W)=1 for each W∈WW∈W, and polynomially solvable in the uniform case of r(W)=r⩾2r(W)=r⩾2 for each W∈WW∈W. In this paper, we show that the problem can be solved in O(m+pn4(r*+logn)) time, even if r(W)⩾2r(W)⩾2 holds for each W∈WW∈W, where n=|V|n=|V|, m=|{{u,v}|(u,v)∈E}|m=|{{u,v}|(u,v)∈E}|, p=|W|p=|W|, and r*=max{r(W)∣W∈W}r*=max{r(W)∣W∈W}.
Journal: Discrete Applied Mathematics - Volume 154, Issue 16, 1 November 2006, Pages 2307–2329