如何在有向图中找到所有强铰接点

Question

我有一个简单的问题：哪种算法可以在有向图中找到所有强铰接点？ 强关节点是一个顶点，如果将其从图形中删除，则会增加牢固连接的组件的数量。

Answer 1

这可以在线性时间（即O（V + E），通过Italiano，Laura和Santaronia（2011）在题为Finding strong bridges and strong articulation points in linear time的论文中描述的算法完成：

给定有向图G，如果边缘的去除增加了G的强连接分量的数量，则边缘是一个坚固的桥。类似地，我们说如果顶点的去除增大了G的强连接的分量数量的顶点是一个强铰接点。 G.在本文中，我们提出了线性时间算法，用于计算有向图的所有强桥梁和所有强铰接点，解决了Beldiceanu等人提出的开放问题。 （2005）[2]。