## 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.