Re:First improvement of fundamental algorithm in 10 years
by Natsu on Monday September 27, 2010 @04:28PM
(#1733251)
I looked around, but the only links I could find appear to be selected textbook chapters that describe old ways of doing it. Even Dr. Dobbs just reprinted the MIT press release. So far, the only useful link I can find is to the scheduled talk and someone already posted that.
EDIT: Incidentally that page does tell us a bit more about the solution than the press release everyone is reprinting. Specifically, it says: "We compute these flows by treating our graph as a network of resistors and solving a sequence of electrical flow problems with varying
resistances on the edges. Each of these may be reduced to the solution of a system of linear equations in a Laplacian matrix, which can be solved in nearly-linear time."
If anyone can find anything more than this link, it would be interesting to me, too: http://www.csail.mit.edu/events/eventcalendar/calendar.php?s...
EDIT: Incidentally that page does tell us a bit more about the solution than the press release everyone is reprinting. Specifically, it says: "We compute these flows by treating our graph as a network of resistors and solving a sequence of electrical flow problems with varying resistances on the edges. Each of these may be reduced to the solution of a system of linear equations in a Laplacian matrix, which can be solved in nearly-linear time."