Minimizing maximum flows in linear graphs
Minimizing maximum flows in linear graphs
复制标题
最小化线性图中的最大流量
DOI：
10.1002/net.3230090405
复制
发表时间：
1979
期刊：
影响因子：
2.1
通讯作者：
G. Magó
中科院分区：
文献类型：
--
作者：
D. Stanat;G. Magó
我们定义一个线性图是一个连通的无圈图，每个节点的度是1或2。考虑线性图中商品从源节点流向汇节点的流问题。每个源节点具有表示要处理的商品的量的指定值，并且每个汇聚节点具有表示其可以吸收的商品的最大量的指定容量;边缘能够承载任意数量的商品。一个解决方案是一组流，它将商品从所有源节点运输到汇节点，而不会过度填充任何汇。如果一个解是极小极大的，即沿任何边的最大流沿着尽可能小，则该解被定义为最优解。我们描述0（n ~ 2）和0（n）算法寻找最优解。
We define a linear graph to be a connected acyclic graph each of whose nodes is of degree one or two. We consider a flow problem in linear graphs in which a commodity flows from source nodes to sink nodes. Each source node has a specified value denoting an amount of a commodity to be disposed of and each sink node has a specified capacity denoting the maximum amount of the commodity it can absorb; edges are capable of carrying an arbitrary quantity of the commodity. A solution is a set of flows which transports the commodity from all source nodes to sink nodes without overfilling any sink. A solution is defined to be optimal if it is minimax, that is, the largest flow along any edge is as small as possible. We describe 0(n2) and 0(n) algorithms for finding optimal solutions.