グラフの次数kのLocalBridge

Question

graphでlocalbridge（k）を見つけるのに最も良いアルゴリズムは何でしょうか？度kのローカルブリッジは、その除去によって、その2つの端点間の最短距離が少なくともkに拡大されるエッジである。

ウィキペディア：代わりに、典型的な実数のhttp://en.wikipedia.org/wiki/Bridge_(interpersonal)#Local_bridge

Answer 1

ランワーシャル - フロイド法のようなすべての-最短パス・コストアルゴリズムが、あなたは距離をタプル(d1,d2)を使用し、d：

• d1最短経路
• d2の長さは、の長さであります第最短経路

ワーシャル - フロイド法に対するこの修正は簡単であるべきです。あなたはすべての-最短パス・コストのアルゴリズムを実行して行われ

は、localbridge(k)エッジは、それらのエッジであるe = {u, v}ようuとv満たすd2 >= k間の距離(1,d2)。