Build a transmuter for a given graph and a spanning tree of it
Give a graph and a spanning tree of it, a transmuter is an auxiliary graph derived from them and can speed up certain operations on original graph. It was invented by 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.
I find myself in need of a transmuter. Unfortunately I don't have access to both documents. Can someone know transmuter and / or have access to the documents elaborate a little bit about transmuter and the algorithm constructing it?
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
unfortunately http://scholar.google.com/scholar?q=%22Sensitivity+Analysis+of+Minimum+Spanning+Trees+and+Shortest+Path+Trees.%22 has no pdf link. see http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/t/Tarjan:Robert_Endre.html in case there are other papers that might help.