• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Induced disjoint paths problem in a planar digraph
【24h】

Induced disjoint paths problem in a planar digraph

机译：平面有向图中的诱导不相交路径问题

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

摘要

As an extension of the disjoint paths problem, we introduce a new problem which we call the induced disjoint paths problem. In this problem we are given a graph G and a collection of vertex pairs {(s(1), t(1)).....(s(k), t(k))}. The objective is to find k paths P-1..... P-k Such that P-i is a path from s(i) to t(i) and P-i and P-j have neither common vertices nor adjacent vertices for any distinct i,j. The induced disjoint paths problem has several variants depending on whether k is a fixed constant or a part of the input, whether the graph is directed or undirected, and whether the graph is planar or not. We investigate the computational complexity of several variants of the induced disjoint paths problem. We show that the induced disjoint paths problem is(i)solvable in polynomial time when k is fixed and G is a directed (or undirected) planar graph, (ii) NP-hard when k = 2 and G is an acyclic directed graph, (iii) NP-hard when k = 2 and G is an undirected general graph. As an application of our first result, we show that we can find in polynomial time certain structures called a "hole" and a "theta" in a planar graph.
机译：作为不相交路径问题的扩展，我们引入了一个新问题，我们将其称为诱导不相交路径问题。在这个问题中，我们得到了图G和一组顶点对{（s（1），t（1））.....（s（k），t（k））}的集合。目的是找到k条路径P-1 ..... P-k，使得P-i是从s（i）到t（i）的路径，并且对于任何不同的i，j，P-i和P-j既不具有公共顶点也不具有相邻顶点。取决于k是固定常数还是输入的一部分，图形是有向的还是无向的，以及图形是否为平面，诱导的不相交路径问题具有多种变体。我们研究了诱导不相交路径问题的几种变体的计算复杂性。我们表明，当k为固定值且G为有向（或无向）平面图时，在（i）多项式时间内可解决诱导不相交路径问题;（k）k = 2且G为非循环有向图时，（ii）NP-hard， （iii）当k = 2且G为无向一般图时为NP-hard。作为我们第一个结果的应用，我们证明了我们可以在多项式时间内在平面图中找到某些称为“孔”和“θ”的结构。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号