クラークソンの2 - 近似加重頂点カバーアルゴリズムランタイム分析

Question

Aは最小加重頂点被覆問題のためのよく知られた2-近似はクラークソンが提案したものです：

クラークソン、ケネス・L.「貪欲アルゴリズムの変更頂点のカバーのために。 Information Processing Letters 16.1（1983）：23-25。

アルゴリズムの読みやすい擬似コードは、hereセクション32.1.2を参照してください。 この論文のアルゴリズムは、実行時の複雑度がO(|E|*log|V|)であり、Eはエッジの集合であり、Vは頂点の集合である。私は彼らがどのようにこの結果を得ているか完全にはわからない。

d（v）をグラフの頂点vとし、w（v）をある重み関数とする。アルゴリズムからの専門的の一部を除く 、アルゴリズムは次のようになります。

while(|E| != 0){ //While there are still edges in the graph 
    Pick a vertex v \in V for which w(v)/d(v) is minimized; 
    for(u : (u,v) \in E){ 
     update w(u); 
     ... 
    } 
    delete v and all edges incident to it from the graph. 
} 

外側のループは、実行時の複雑さの用語|E|を生成します。つまり、ある割合を最小にする頂点のリストから頂点を選ぶことは、log nの時間に行うことができます。私が知る限り、値のリストから最小値を見つけるには、log nではなく、n-1の比較が必要です。最後に、内側forループはvのすべての隣接ノードに対して実行されるため、n-1が支配するd（v）の複雑さが生じます。したがって、アルゴリズムの実行時の複雑さはO(|E|*|V|)であると結論づけます。 私はここで何が欠けていますか？

Answer 1

w（v）/ d（v）で順序付けられた平衡二分探索木に頂点を保持する。最小値を求めることはO（log | V |）です。エッジuvを削除するたびに、uのキーを削除して（新しいキーでツリーに再挿入する）時間O（log | V |）の時間がかかります。これらの各ステップはせいぜい| E |回。