...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Arc-disjoint paths and trees in 2-regular digraphs
【24h】

Arc-disjoint paths and trees in 2-regular digraphs

机译：2正则图的不相交路径和树木

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

摘要

An out-branching (in-branching) Bs+(Bs-) in a digraph D is a connected spanning subdigraph of D in which every vertex x≠s has precisely one arc entering (leaving) it and s has no arcs entering (leaving) it. We settle the complexity of the following two problems: Given a 2-regular digraph D, decide whether it contains two arc-disjoint branchings Bu+, Bv-.Given a 2-regular digraph D, decide whether it contains an out-branching Bu+ such that D remains connected after removing the arcs of Bu+. Both problems are NP-complete for general digraphs (Bang-Jensen (1991) [1], Bang-Jensen and Yeo (2012) [7]). We prove that the first problem remains NP-complete for 2-regular digraphs, whereas the second problem turns out to be polynomial when we do not prescribe the root in advance. The complexity when the root is prescribed in advance is still open. We also prove that, for 2-regular digraphs, the second problem is in fact equivalent to deciding whether D contains two arc-disjoint out-branchings.
机译：有向图D中的分支（分支内）Bs +（Bs-）是D的连通跨越子图，其中每个顶点x≠s都有一个弧进入（离开），而s没有弧进入（离开）它。我们解决了以下两个问题的复杂性：给定2个正则图D，确定它是否包含两个不相交的分支Bu +，Bv-。给定2个正则图D，决定它是否包含一个向外分支的Bu +，例如去除Bu +的弧后，D保持连接。对于一般有向图，这两个问题都是NP完全的（Bang-Jensen（1991）[1]，Bang-Jensen and Yeo（2012）[7]）。我们证明了第一个问题对于2正则图有NP完全性，而当我们不预先规定根时，第二个问题证明是多项式。预先指定根的复杂性仍然是未知的。我们还证明，对于2正则有向图，第二个问题实际上等同于确定D是否包含两个弧形不相交的分支。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号