کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656811 1632983 2015 44 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Criticality for multicommodity flows
ترجمه فارسی عنوان
انتقادات برای جریانهای چند کاره
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

For k≥1k≥1, the k-commodity flow problem is, we are given k pairs of vertices in a graph G, and we ask whether there exist k flows in the graph, where
• the ith flow is between the ith pair of vertices, and has total value one; and
• for each edge e, the sum of absolute values of the flows along e is at most one. We prove that for all k   there exists n(k)n(k) such that if G is connected, and contraction-minimal such that the k  -commodity flow problem is infeasible (that is, minimal in the sense that contracting any edge makes the problem feasible) then |V(G)|+|E(G)|≤n(k)|V(G)|+|E(G)|≤n(k).For integers k,p≥1k,p≥1, the (k,p)(k,p)-commodity flow problem   is as above, with the extra requirement that the flow value of each flow along each edge is a multiple of 1/p1/p. We prove that if p>1p>1, and G   is connected, and contraction-minimal such that the (k,p)(k,p)-commodity flow problem is infeasible, then |V(G)|+|E(G)|≤n(k)|V(G)|+|E(G)|≤n(k), with the same n(k)n(k) as before, independent of p  . In contrast, when p=1p=1 there are arbitrarily large contraction-minimal instances, even when k=2k=2.We give some other corollaries of the same approach, including
• a proof that for all k≥0k≥0 there exists p>0p>0 such that every feasible k  -commodity flow problem has a solution in which all flow values are multiples of 1/p1/p, and
• a very simple polynomial-time algorithm to solve the (k,p)(k,p) multicommodity flow problem when p>1p>1.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 110, January 2015, Pages 136–179
نویسندگان
,