2003 · 125 citations · 20 references
ComputingComputer ScienceMathematicsAlgorithmsDistributed SystemsTheory Of ComputationComplexity TheoryComputational ComplexityDistributed AlgorithmsDistributed ComputingRoutingRouting AlgorithmsComputational Complexity Of DecompositionExponential Time ComplexityMulticommodity FlowOblivious RoutingPolynomial-time Algorithms
Racke recently gave a remarkable proof showing that any undirected multicommodity ow problem can be routed in an oblivious fashion with congestion that is within a factor of O(log n) of the best o-line solution to the problem. He also presented interesting applications of this result to distributed computing. Maggs, Miller, Parekh, Ravi and Wu have shown that such a decomposition also has an application to speeding up iterative solvers of linear systems.
20
Universal schemes for parallel communication
Leslie G. Valiant, Gordon Brebner · 1981 · 631 citations