论文标题
用于获得单一连接子图的算法的实验研究
An experimental study of algorithms for obtaining a singly connected subgraph
论文作者
论文摘要
如果对任何两个顶点V，u的u，则有向图G =（V，e）单独连接，有向图G的最多包含一个从V到U的一个简单路径。在本文中，我们研究了不同的算法，以找到可行但必然是针对以下问题的最佳解决方案。鉴于有向的无环g =（v，e），找到了最小尺寸的E子集h，因此单独连接了子图（V，E-H）。此外，我们证明该问题可以在多项式时间内解决特殊的有向图。
A directed graph G = (V,E) is singly connected if for any two vertices v, u of V, the directed graph G contains at most one simple path from v to u. In this paper, we study different algorithms to find a feasible but necessarily optimal solution to the following problem. Given a directed acyclic graph G = (V, E), find a subset H of E of minimum size such that the subgraph (V, E-H) is singly connected. Moreover, we prove that this problem can be solved in polynomial time for a special kind of directed graphs.
