首页> 外文会议>Frontiers in algorithmics >Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains
【24h】

Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains

机译:具有加法损耗和增益的网络中的最短路径和最大流量问题

获取原文
获取原文并翻译 | 示例

摘要

We introduce networks with additive losses and gains on the arcs. If a positive flow of x units enter an arc a, then x + g(a) units exit. Arcs may increase or consume flow, i.e., they are gainy or lossy. Such networks have various applications, e.g., in financial analysis, transportation, and data communication.rnProblems in such networks are generally intractable. In particular, the shortest path problem is NP-hard. However, there is a pseudo-polynomial time algorithm for the problem with nonnegative costs and gains. The maximum flow problem is strongly NP-hard, even in unit-gain networks and in networks with integral capacities and loss at most three, and is hard to approximate. However, it is solvable in polynomial time in unit-loss networks using the Edmonds-Karp algorithm.rnOur NP-hardness results contrast efficient polynomial time solutions of path and flow problems in standard and in so-called generalized networks with multiplicative losses and gains.
机译:我们介绍了具有附加损耗和弧形增益的网络。如果x单位的正向流量输入弧a,则x + g(a)单位退出。电弧可能会增加或消耗流量,即它们是有损耗的或有损耗的。这样的网络具有各种应用,例如在财务分析,运输和数据通信中。这种网络中的问题通常是棘手的。特别地,最短路径问题是NP困难的。但是,对于具有非负成本和收益的问题,有一个伪多项式时间算法。即使在单位增益网络以及具有积分容量和最多三个损耗的网络中,最大流量问题也具有很强的NP难度,并且很难近似。但是,它可以使用Edmonds-Karp算法在单位损失网络中的多项式时间中求解。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号