h*********y
发帖数: 9 | 1 We are given an undirected graph G=(V,E) with capacities on each edge.We are
given k source-destination pairs (s(i),t(i))and a required rate r(i) for the
pair(s(i),t(i)).we would like to determine whether we can route the required
rates for all source-destination pairs subject to the additional constraint
that traffic for each pair ( s(i),t(i) )flow along a single path from s(i) to
t(i).
In the partition problem,we are given a set X={x1,x2,...xn} of n integers, and
asked to determine whether the | k**y
发帖数: 320 | 2 建议以后post中文,看懂题比做出来还要费时间,难怪没人回
题目好象是这样的:
有个已知的NP问题:k个数,挑出某些让它们的和(sum)是整数n.
这个问题可以reduce到bin packing,所以是NP.
现在问题是有个图(V,E),每条边e有个capacity,c(e).V其中有
k个pair{s(i),t(i)},要求建立从s(i)到t(i)的一个route,流量
是r(i).现在要证明这个问题也是NP.
解决:
对k个数做个图,V={s(i),t(i),S,T}.c(s(i),S)=c(t(i),T)=r(i)
S到T有两条边,c(S,T)1=n,c(S,T)2=sum(r(i))-n.
完了.
【在 h*********y 的大作中提到】
: We are given an undirected graph G=(V,E) with capacities on each edge.We are
: given k source-destination pairs (s(i),t(i))and a required rate r(i) for the
: pair(s(i),t(i)).we would like to determine whether we can route the required
: rates for all source-destination pairs subject to the additional constraint
: that traffic for each pair ( s(i),t(i) )flow along a single path from s(i) to
: t(i).
: In the partition problem,we are given a set X={x1,x2,...xn} of n integers, and
: asked to determine whether the
|
|
