グラフとそのスパニングツリーを与えると、トランスミューターはそれらから派生した補助グラフであり、元のグラフでの特定の操作を高速化できます。Tarjanによって発明されました：
Robert E. Tarjan. Applications of Path Compression on Balanced Trees. Journal of the ACM, 26(4):690–715, 1979.
Robert E. Tarjan. Sensitivity Analysis of Minimum Spanning Trees and Shortest Path Trees. Information Processing Letters, 14(1):30–33, 1982.
私はトランスミューターを必要としていることに気づきました。残念ながら、私は両方のドキュメントにアクセスできません。誰かがトランスミューターを知っているか、および/またはトランスミューターとそれを構築するアルゴリズムについて少し詳しく説明しているドキュメントにアクセスできますか？
http://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/applications%20of%20path%20compression.pdf from http://scholar.google.com/scholar?q=%22Applications+of + Path + Compression + on + Balanced + Trees。％22 from http://www.informatik.uni-trier.de/~ley/db/journals/jacm/jacm26.html#Tarjan79
残念ながら、 http： //scholar.google.com/scholar？q =％22Sensitivity + Analysis + of + Minimum + Spanning + Trees + and + Shortest + Path + Trees。％22にはPDFリンクがありません。他に役立つ論文がある場合は、http：//www.informatik.uni-trier.de/~ley/db/indices/a-tree/t/Tarjan：Robert_Endre.htmlを参照してください。