12 citations · 28 across the 4 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2010
Smoothed Analysis of Balancing Networks
Tobias Friedrich, Thomas Sauerwald, Dan Vilenchik
In a balancing network each processor has an initial collection of unit-size jobs (tokens) and in each round, pairs of processors connected by balancers split their load as evenly…
cs.DS2006★ 12 cited
An O(n^{2.75}) algorithm for online topological ordering
Deepak Ajwani, Tobias Friedrich, Ulrich Meyer
We present a simple algorithm which maintains the topological order of a directed acyclic graph with n nodes under an online edge insertion sequence in O(n^{2.75}) time, independen…