论文标题
计算所有$ s $ - $ t $桥梁和发音点简化
Computing all $s$-$t$ bridges and articulation points simplified
论文作者
论文摘要
鉴于有向图的$ g $和一对节点$ s $和$ t $，$ s $ - $ t $ bridge的$ g $是一个边缘，其删除破坏了$ g $的所有$ s $ - $ t $路径。同样，$ S $ - $ t $发音点的$ g $是一个节点，其删除破坏了$ g $的所有$ s $ - $ t $路径。计算所有$ s $ -t $ t $ bridges的顺序为$ g $（以及$ s $ - $ t $表达点）是一个基本的图形问题，可以使用经典的Min-CUT算法在线性时间解决。 当处理单位尺寸的切割时（$ s $ - $ t $ bridges）可以简化该算法的单个图形遍历，从$ s $到$ t $避免使用任意$ s $ -t $ t $路径，该路径在$ s $ -t $ t $ bridges中被打断。此外，相应的证据也简化了，使其独立于网络流理论。
Given a directed graph $G$ and a pair of nodes $s$ and $t$, an $s$-$t$ bridge of $G$ is an edge whose removal breaks all $s$-$t$ paths of $G$. Similarly, an $s$-$t$ articulation point of $G$ is a node whose removal breaks all $s$-$t$ paths of $G$. Computing the sequence of all $s$-$t$ bridges of $G$ (as well as the $s$-$t$ articulation points) is a basic graph problem, solvable in linear time using the classical min-cut algorithm. When dealing with cuts of unit size ($s$-$t$ bridges) this algorithm can be simplified to a single graph traversal from $s$ to $t$ avoiding an arbitrary $s$-$t$ path, which is interrupted at the $s$-$t$ bridges. Further, the corresponding proof is also simplified making it independent of the theory of network flows.
