ICS Theory Group

CompSci 269S, Winter 2008: Theory Seminar

Apr 18, 2008, 1:00pm in Bren Hall 1423

Graph Algorithms in PEM: Part II

presented by Nodari Sitchinava


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.