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?

Answers


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.


Need Your Help

Regex to extract multiple sentences while discarding a specific one

c# regex

In: preferences = 'Hello my name is paul. I hate puzzles.'

bind_result() not binding variables

php mysql sql

The following code is producing the error: Notice: Undefined variable: morrisons.