Abstract:
This is the second part in the two part series on graph algorithms in the Parallel External Memory model. I will present algorithms for finding connected and bi-connected components, minimum spanning trees and ear decomposition in graphs; tree contraction, expression tree evaluation and lowest common ancestor queries on trees. All these solutions use Euler tour technique as the building block just like in the PRAM algorithms. Therefore, I'll review this technique and simple problems one can solve with it in parallel.
This is joint work with Lars Arge and Michael Goodrich.