...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >On the maximum disjoint paths problem on edge-colored graphs
【24h】

On the maximum disjoint paths problem on edge-colored graphs

机译：关于边色图的最大不相交路径问题

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

摘要

We study the problem of finding the maximum number of disjoint uni-color paths in an edge-colored graph. We show the NP-hardness and the approximability and present approximation and exact algorithms. We also study the length-bounded version of the problem, in which the numbers of edges of the found paths are required to be upper bounded by a fixed integer l. It is shown that the problem can be solved in polynomial time for l≤3 and is NP-hard for l<4. We also show that the problem can be approximated with ratio (l-1)2+ε in polynomial time for any ε>0. Particularly, for l=4, we present an efficient 2-approximation algorithm.
机译：我们研究在边缘彩色图中找到最大不相交单色路径的问题。我们展示了NP硬度和逼近度，并给出了逼近和精确算法。我们还研究了问题的有界版本，在该版本中，所找到路径的边数要求以固定整数l为上限。结果表明，对于l≤3，可以在多项式时间内解决，对于l <4，则是NP-难的。我们还表明，对于任意ε> 0，该问题都可以用多项式时间内的比率（l-1）2 +ε来近似。特别地，对于l = 4，我们提出了一种有效的2近似算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号