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

Long press drop down menu in windows phone 7?

c# windows-phone-7

I have a databound application with data the user can add or remove. I would like the users to option to remove a displayed item on screen by long pressing it and then selecting delete from a drop ...

Spark Scroller, limit to vertical scrolling

flex actionscript flex4 scroll scroller

I have a Spark Scroller within my View because I have a lot of content and require vertical scrolling. I current have some labels that get data from my dataProvider, and the strings are sometimes l...

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.