...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Polynomial-time algorithms for special cases of the maximum confluent flow problem
【24h】

Polynomial-time algorithms for special cases of the maximum confluent flow problem

机译：最大合流问题特殊情况的多项式时间算法

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

摘要

A flow on a directed network is said to be confluent if the flow uses at most one outgoing arc at each node. Confluent flows arise naturally in destination-based routing. We study the maximum confluent flow problem (MaxConf) with a single commodity but multiple sources and sinks and heterogeneous arc capacities. It was recently shown that MaxConf is NP-hard even on trees. We improve the classification of easy and hard confluent flow problems by providing polynomial-time algorithms for outerplanar graphs with a single sink, as well as trees with a constant number of either sources or sinks. Furthermore, we present an FPTAS for graphs with bounded treewidth.
机译：如果定向网络上的流在每个节点上最多使用一个出弧，则称该流为合流的。在基于目的地的路由中自然会产生汇合流。我们研究了单一商品，多个源和汇以及不同电弧容量的最大汇流问题（MaxConf）。最近显示，即使在树上，MaxConf也是NP坚硬的。通过为具有单个接收器的外平面图以及具有恒定数量的源或接收器的树提供多项式时间算法，我们改进了易汇流和硬汇流问题的分类。此外，我们为具有有限树宽的图提供了FPTAS。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号