A polynomial-time tree decomposition to minimize congestion
Chris Harrelson, Kirsten W. Hildrum, Satish S. Rao · 2003
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.