2 papers
cs.DS2008
Average-Case Analysis of Online Topological Ordering
Deepak Ajwani, Tobias Friedrich
Many applications like pointer analysis and incremental compilation require maintaining a topological ordering of the nodes of a directed acyclic graph (DAG) under dynamic updates.…
math.CO2007
Deterministic Random Walks on the Two-Dimensional Grid
Benjamin Doerr, Tobias Friedrich
Jim Propp's rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. W…