On enumerating all minimal solutions of feedback problems
On enumerating all minimal solutions of feedback problems
复制标题
枚举反馈问题的所有最小解
DOI：
10.1016/s0166-218x(00)00339-5
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Ewald Speckenmeyer
中科院分区：
文献类型：
--
作者：
B. Schwikowski;Ewald Speckenmeyer
我们提出了一种生成有向图G=（V，E）的所有（包含式）最小反馈顶点集的算法。G的反馈顶点集生成的多项式延迟为O （|V|2(|V|+|E|)）。我们进一步表明，基础技术可以被定制为无向情况和有向反馈弧集问题的所有最小解，两者都具有多项式延迟O (|V| |E| （|V|+|E|）。最后，我们证明了计算最小反馈弧集的个数是#P-hard。
We present an algorithm that generates all (inclusion-wise) minimal feedback vertex sets of a directed graph G=(V,E). The feedback vertex sets of G are generated with a polynomial delay of O (|V|2(|V|+|E|)) . We further show that the underlying technique can be tailored to generate all minimal solutions for the undirected case and the directed feedback arc set problem, both with a polynomial delay of O (|V| |E| (|V|+|E|) . Finally, we prove that computing the number of minimal feedback arc sets is #P-hard.