A polynomial-time tree decomposition to minimize congestion

Chris Harrelson, Kirsten Hildrum, Satish Rao

2003 · 125 citations · 20 references

Concepts

Abstract

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.

References

20