• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual Symposium on Theoretical Aspects of Computer Science(STACS 2004); 20040325-20040327; Montpellier; FR >Integral Symmetric 2-Commodity Flows
【24h】

Integral Symmetric 2-Commodity Flows

机译：积分对称2-商品流

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

摘要

We study integral 2-commodity flows in networks with a special characteristic, namely symmetry. We show that the Symmetric 2-Commodity Flow Problem is in P, by proving that the cut criterion is a necessary and sufficient condition for the existence of a solution. We also give a polynomial-time algorithm whose complexity is 6C_(flow) + O(|A|), where C_(flow) is the time complexity of your favorite flow algorithm (usually in O(|V| x|A|)). Our result closes an open question in a surprising way, since it is known that the Integral 2-Commodity Flow Problem is NP-complete for both directed and undirected graphs. This work finds application in optical telecommunication networks.
机译：我们研究具有特殊特征（即对称性）的网络中的积分2商品流。通过证明割准则是解的存在的必要和充分条件，我们证明了对称2-商品流问题在P中。我们还给出了多项式时间算法，其复杂度为6C_（flow）+ O（| A |），其中C_（flow）是您最喜欢的流算法的时间复杂度（通常为O（| V | x | A |） ）。我们的结果以令人惊讶的方式结束了一个悬而未决的问题，因为众所周知，有向图和无向图的积分2商品流问题都是NP完全的。这项工作在光通信网络中得到了应用。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号