Euler tour technique とは

Leonhard Eulerにちなんで命名されたオイラーツアーテクニック(ETT)は、木を表現するためのグラフ理論の1つの方法です。ツリーは、ツリー内の各エッジに対して2つの有向エッジを含む有向グラフとして表示されます。ツリーは、木のEuler Tour表現(Euler Tour Representation)として知られる有向グラフのオイラー回路として表現することができます。 ETTは、アルゴリズムグラフ理論における一般的な問題に対する解の効率的かつ並列な計算を可能にする。それは1984年にTarjanとVishkinによって導入されました。