K-辺連結グラフ
辺連結度を決定するための多項式時間アルゴリズムが存在する。 ある簡単なアルゴリズムは、全てのペア (u,v) に対して、G 内のすべての辺の容量が両方向に対して 1 に定められているような、 u から v への最大フローを決定するものである。 グラフが k-辺連結であるための必要十分条件は、任意ペア (u,v) に対して u から v への最大フローは最小でも k であること、すなわち k が全ての (u,v) の中での最小の u-v-フローであることである。
V をグラフに含まれる頂点の数としたとき、この簡単なアルゴリズムでは O ( V 2 ) {\displaystyle O(V^{2})} 回の最大フロー問題の反復が行われ、時間 O ( V 3 ) {\displaystyle O(V^{3})} 内に解決される。したがって、この簡単なアルゴリズムの計算量は、総合すると O ( V 5 ) {\displaystyle O(V^{5})} となる。
改善されたアルゴリズムでは、任意の固定された u と、固定されていない任意の v からなる全てのペア (u,v) に対する最大フロー問題を解く。このアルゴリズムでは計算量は O ( V 4 ) {\displaystyle O(V^{4})} へと減らされており、適切なものである。なぜならば、もし容量が k より少ないカットが存在するのなら、それは u を他の頂点から切り離すからである。