...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Optimization >Path packing and a related optimization problem
【24h】

Path packing and a related optimization problem

机译：路径打包和相关的优化问题

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

摘要

Let G be a supply graph, with the node set N and edge set E, and (T,S) be a demand graph, with T?N, S∩E=?. Observe paths whose end-vertices form pairs in S (called S-paths). The following path packing problem for graphs is fundamental: what is the maximal number of S-paths in G? In this paper this problem is studied under two assumptions: (a) the node degrees in N?T are even, and (b) any three distinct pairwise intersecting maximal stable sets A,B,C of (T,S) satisfy A∩B=B∩C=A∩C (this condition was defined by A. Karzanov in Linear Algebra Appl. 114–115:293–328, 1989). For any demand graph violating (b) the problem is known to be NP-hard even under (a), and only a few cases satisfying (a) and (b) have been solved. In each of the solved cases, a solution and an optimal dual object were defined by a certain auxiliary “weak” multiflow optimization problem whose solutions supply constructive elements for S-paths and concatenate them into an S-path packing by a kind of matching.
机译：令G为供给图，节点集为N，边集为E，（T，S）为需求图，其中T？N，S？E =?。观察末端顶点在S中成对的路径（称为S路径）。图的以下路径打包问题是基本问题：G中S路径的最大数量是多少？本文在两个假设下研究这个问题：（a）N？T中的节点度是偶数，和（b）（T，S）的任何三个不同的成对相交的最大稳定集A，B，C满足A∩ B =B∩C=A∩C（此条件由A. Karzanov在Linear Algebra Appl。114–115：293–328，1989中定义）。对于任何违反（b）的需求图，即使在（a）情况下，该问题也是已知的NP难题，并且仅解决了满足（a）和（b）的少数情况。在每种已解决的情况下，解决方案和最优对偶对象都是由某个辅助“弱”多流优化问题定义的，该问题的解决方案为S路径提供了构造性元素，并通过一种匹配将它们连接为S路径包装。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号