...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >PARAMETERIZED TRACTABILITY OF EDGE-DISJOINT PATHS ON DIRECTED ACYCLIC GRAPHS
【24h】

PARAMETERIZED TRACTABILITY OF EDGE-DISJOINT PATHS ON DIRECTED ACYCLIC GRAPHS

机译：直接循环图上边离合路径的参数化可追踪性

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

摘要

Given a graph and terminal pairs (s_i,t_i), i ε [k], the edge-disjoint paths problem is to determine whether there exist siti paths, i ε [k], that do not share any edges. We consider this problem on acyclic digraphs. It is known to be NP-complete and solvable in time n~o(k) where n is the number of nodes. It has been a long-standing open question whether it is fixed-parameter tractable in k, i.e., whether it admits an algorithm with running time of the form f(k)n~o(1). We resolve this question in the negative: we show that the problem is W[l]-hard, hence unlikely to be fixed-parameter tractable. In fact it remains W[l]-hard even if the demand graph consists of two sets of parallel edges. On a positive side, we give an O(m + k~o(1)k! n) algorithm for the special case when G is acyclic and G + H is Eulerian, where H is the demand graph. We generalize this result (1) to the case when G + H is "nearly" Eulerian, and (2) to an analogous special case of the unsplittable flow problem, a generalized version of disjoint paths that has capacities and demands.
机译：给定图和终端对（s_i，t_i）iε[k]，边不相交的路径问题是确定是否存在不共享任何边的siti路径iε[k]。我们在无环有向图中考虑这个问题。已知它是NP完全的，并且可以在时间n〜o（k）内求解，其中n是节点数。它是否在k中是固定参数易处理的，这是一个长期存在的问题，即它是否允许运行时间形式为f（k）n〜o（1）的算法。我们否定地解决了这个问题：我们证明问题是W [l]难题，因此不可能是固定参数可处理的。实际上，即使需求图由两组平行边组成，它仍然具有W [l]的难度。从积极的方面来说，对于G是非循环且G + H是欧拉式的特殊情况，我们给出O（m + k〜o（1）k！n）算法，其中H是需求图。我们将这个结果推广为（1）到G + H接近“欧拉”的情况，以及（2）推广到不可分裂流动问题的类似特殊情况，即具有能力和需求的不相交路径的广义形式。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号