2

u -> v含意グラフは、各ノードに true または false のいずれかが割り当てられ、任意のエッジがそれを意味する有向グラフですif u is true then v is true

O(n^2)一般的な含意グラフで割り当てを見つける簡単なアルゴリズムと、いくつかの特殊なケース ( 2-SAT問題O(n)から生じる含意グラフなど) のアルゴリズムを知っています。

O(n)それで、含意グラフの割り当てを見つけるアルゴリズムがあるかどうか疑問に思っていましたか?

4

1 に答える 1

1

タージャン強連結成分法は、2-SAT インスタンスの変換によって生成されたものだけでなく、すべての含意グラフに適用できるため、含意グラフの満足のいく割り当てを見つけることができます。この方法は少数のグラフ変換ステップで構成されており、そのすべてに入力のサイズに比例した時間が必要です。したがって、アルゴリズムは全体として O(n) ランタイムを必要とします。

于 2014-09-21T00:33:27.910 に答える