切断された有向グラフが強く接続されるためのエッジの最小数

Question

頂点がV={a,b,c,d}であり、エッジがE={(a->b),(a->c)}で、頂点がdである切断有向グラフG={V,E}の例を考えてみましょう。ここでの答えによると

：（Minimal addition to strongly connected graph）は、このグラフを確保するために必要なエッジの最小数はであることが判明開始と終了の頂点すなわち、これらのエッジを追加する場所を見つけるための方法3.

このグラフのエッジの？

Answer 1

これは驚くほど微妙な問題です。 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 
} 
}