ICS Theory Group

February 6, Winter 2009: Theory Seminar

1:00pm in 253 ICS

A New Approach to Incremental Topological Ordering

by Michael A. Bender, Jeremy T. Fineman, and Seth Gilbert, appeared in SODA '09.

Presented by Darren Strash, UC Irvine

Consider the following problem: We begin with a graph consisting of n nodes and zero edges. An adversary adds m edges to the graph, one edge at a time. Throughout this process, we would like to maintain a topological ordering of the graph. I will discuss a recent paper which presents a new algorithm that has a total running time of O(n2 log n) for maintaining the topological ordering throughout all the edge insertions.