• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Generalized max flow in series-parallel graphs
【24h】

Generalized max flow in series-parallel graphs

机译：串联-平行图中的广义最大流量

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In the generalized max flow problem, the aim is to find a maximum flow in a generalized network, i.e., a network with multipliers on the arcs that specify which portion of the flow entering an arc at its tail node reaches its head node. We consider this problem for the class of series-parallel graphs. First, we study the continuous case of the problem and prove that it can be solved using a greedy approach. Based on this result, we present a combinatorial algorithm that runs in O(nm+mlogm) time, where m is the number of arcs, and a dynamic programming algorithm with running time O(mlogm). For the integral version of the problem, which is known to be NP-complete, we present a pseudo-polynomial algorithm.
机译：在广义最大流问题中，目的是在广义网络中找到最大流，即在弧上具有乘法器的网络，该乘子指定在流的尾端节点处进入弧的流的哪个部分到达其头节点。对于串联-平行图类，我们考虑这个问题。首先，我们研究问题的连续情况，并证明可以使用贪婪方法解决问题。基于此结果，我们提出了一种在O（nm + mlogm）时间内运行的组合算法，其中m是弧的数量，以及一种动态算法，其运行时间为O（mlogm）。对于已知为NP完全的问题的整数形式，我们提出了一个伪多项式算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号