Let Electric Current Pick the Path

In a paper recognized as the best at the ACM-SIAM Symposium on Discrete Algorithms in January, MIT researchers describe a new theoretical algorithm that can reduce the number of operations needed to solve the max-flow problem.

The sizes of graphs being studied has exploded since the advent of the Internet, and previous max-flow algorithms attacked the problem one path at a time. The MIT team, however, viewed the graph as a collection of electrical resistors, and imagined letting current flow through the network.

Says Jonathan Kelner, one of the researchers:

Electrical current doesn’t pick just one path, it will send a little bit of current over every resistor on the network. So it probes the whole graph globally, studying many paths at the same time.

Read MIT's coverage.