algorithm - 断开有向图使其牢固连接的最小边数

以顶点G={V,E}且边V={a,b,c,d}且顶点E={(a->b),(a->c)}被隔离的不连通有向图为例。
根据这里的答案：（Minimal addition to strongly connected graph），确保此图的最小边数为3。
如何找到将这些边添加到何处，即图中边的起点和终点？

最佳答案

这是一个非常微妙的问题。Eswaran和Tarjan（见下文）是第一个宣称它是线性时间算法的人，但是Raghavan发现并纠正了一个错误（A note on Eswaran And Tarjan's algorithm for the strong connectivity augmentation problem）。链接的pdf文章包含了对修正算法的完整处理。

@article{doi:10.1137/0205044,
author = {Kapali P. Eswaran and R. Endre Tarjan},
title = {Augmentation Problems},
journal = {SIAM Journal on Computing},
volume = {5},
number = {4},
pages = {653-665},
year = {1976},
doi = {10.1137/0205044},
URL = {
        http://dx.doi.org/10.1137/0205044
},
eprint = {
        http://dx.doi.org/10.1137/0205044
}
}

关于algorithm - 断开有向图使其牢固连接的最小边数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43205606/