k-distinct in- and out-branchings in digraphs
k-distinct in- and out-branchings in digraphs
复制标题
有向图中的 k-不同的内分支和外分支
DOI：
10.1016/j.jcss.2018.01.003
复制
发表时间：
2018
影响因子：
1.1
通讯作者：
Gutin G
中科院分区：
文献类型：
--
作者：
Gutin G
一个有向图的一个出枝和一个入枝，如果它们中的每一个在另一个中不存在卡，则称为-不同的。Bang-Jensen，Saurabh和Simonsen（2016）证明了当参数为k时，决定强连通有向图Dhask-不同的出分支和入分支是否是固定参数可处理的问题。他们问是否问题仍然FPT时，扩展到任意有向图。Bang-Jensen和Yeo（2008）提出，当出分支和入分支具有相同的根时，是否存在相同的问题。通过将这两个问题与有向图是否有至少kleaves（叶子是出度为零的顶点）的出分支问题联系起来，我们首先解决了Bang-Jensen和Yeo（2008）的问题。然后，我们开发了一个新的有向图分解，并使用它证明了Bang-Jensen et al.（2016）的问题对于所有有向图都是FPT。
An out-branching and an in-branching of a digraphDare calledk-distinct if each of them haskarcs absent in the other. Bang-Jensen, Saurabh and Simonsen (2016) proved that the problem of deciding whether a strongly connected digraphDhask-distinct out-branching and in-branching is fixed-parameter tractable (FPT) when parameterized byk. They asked whether the problem remains FPT when extended to arbitrary digraphs. Bang-Jensen and Yeo (2008) asked whether the same problem is FPT when the out-branching and in-branching have the same root. By linking the two problems with the problem of whether a digraph has an out-branching with at leastkleaves (a leaf is a vertex of out-degree zero), we first solve the problem of Bang-Jensen and Yeo (2008). We then develop a new digraph decomposition and using it prove that the problem of Bang-Jensen et al. (2016) is FPT for all digraphs.