...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On spanning galaxies in digraphs (Conference Paper)
【24h】

On spanning galaxies in digraphs (Conference Paper)

机译：关于有向图的跨越星系（会议论文）

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

摘要

In a directed graph, a star is an arborescence with at least one arc, in which the root dominates all the other vertices. A galaxy is a vertex-disjoint union of stars. In this paper, we consider the Spanning Galaxy problem of deciding whether a digraph D has a spanning galaxy or not. We show that although this problem is NP-complete (even when restricted to acyclic digraphs), it becomes polynomial-time solvable when restricted to strong digraphs. In fact, we prove that restricted to this class, the Spanning Galaxy problem is equivalent to the problem of deciding whether a strong digraph has a strong subdigraph with an even number of vertices. We then show a polynomial-time algorithm to solve this problem. We also consider some parameterized version of the Spanning Galaxy problem. Finally, we improve some results concerning the notion of directed star arboricity of a digraph D, which is the minimum number of galaxies needed to cover all the arcs of D. We show in particular that dst(D)≤Δ(D)+1 for every digraph D and that dst(D)≤Δ(D) for every acyclic digraph D.
机译：在有向图中，星形是具有至少一个弧的树状结构，其中根支配所有其他顶点。星系是恒星的顶点不相交的并集。在本文中，我们考虑了跨度星系问题，即确定有向图D是否具有跨度星系。我们表明，尽管此问题是NP完全的（即使仅限于无环有向图），但当仅限于强有向图时，它变为多项式时间可解。实际上，我们证明了跨度星系问题仅限于此类，它等于确定一个强有向图是否具有一个具有偶数个顶点的强有向图。然后，我们展示了多项式时间算法来解决此问题。我们还考虑了Spanning Galaxy问题的一些参数化版本。最后，我们改进了关于有向图D的有向星空度的概念的一些结果，这是覆盖D的所有弧所需的最小星系数。我们特别证明dst（D）≤Δ（D）+1对于每个有向图D，并且每个非循环有向图D的dst（D）≤Δ（D）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号