由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Science版 - NP-hard
相关主题
An optimization problem菜鸟求救
y2k imo (2)4-阶龙格库塔子程序
算24问题扩展Re: 再问:Human genom project测的是谁的?
An abstract on protein folding[转载]Mathematica函数及使用方法(6)
simple problems of heat transferRe: 帮个忙
Re: 问个几率传递的问题?[转载] how do you do integer division?
Re: 数学高手请进!!questions
Re: 请教一个联合分布的问题Re: 谁有fast Fourire transform的子程序)
相关话题的讨论汇总
话题: given话题: np话题: pair话题: pairs话题: determine
进入Science版参与讨论
1 (共1页)
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

1 (共1页)
进入Science版参与讨论
相关主题
Re: 谁有fast Fourire transform的子程序)simple problems of heat transfer
y2k imo (4)Re: 问个几率传递的问题?
Re: Integer OptimizationRe: 数学高手请进!!
Is the world deterministic?Re: 请教一个联合分布的问题
An optimization problem菜鸟求救
y2k imo (2)4-阶龙格库塔子程序
算24问题扩展Re: 再问:Human genom project测的是谁的?
An abstract on protein folding[转载]Mathematica函数及使用方法(6)
相关话题的讨论汇总
话题: given话题: np话题: pair话题: pairs话题: determine