Interesting in that it appears to claim that representing a graph as an array is a new idea!
http://nextbigfuture.com/2010/09/mit-yale-and-usc-have-better-max-flow.html The New Algorithm Kelner, CSAIL grad student Aleksander Madry, math undergrad Paul Christiano, and Professors Daniel Spielman and Shanghua Teng of, respectively, Yale and USC, have taken a fundamentally new approach to the problem. They represent the graph as a matrix, which is math-speak for a big grid of numbers. Each node in the graph is assigned one row and one column of the matrix; the number where a row and a column intersect represents the amount of stuff that may be transferred between two nodes. In the branch of mathematics known as linear algebra, a row of a matrix can also be interpreted as a mathematical equation, and the tools of linear algebra enable the simultaneous solution of all the equations embodied by all of a matrix's rows. By repeatedly modifying the numbers in the matrix and re-solving the equations, the researchers effectively evaluate the whole graph at once. This approach, which Kelner will describe at a talk at MIT's Stata Center on Sept. 28, turns out to be more efficient than trying out paths one by one. If N is the number of nodes in a graph, and L is the number of links between them, then the execution of the fastest previous max-flow algorithm was proportional to (N + L)(3/2). The execution of the new algorithm is proportional to (N + L)(4/3). The researchers haven't in fact written a program that implements their algorithm, and in practice, the performance of an algorithm can depend on factors like how efficiently it's coded and how well it manages memory. But in theory, for a network like the Internet, which has about 100 billion nodes, the new algorithm could solve the max-flow problem 100 times faster than its predecessor. The immediate practicality of the algorithm, however, is not what impresses John Hopcroft, the IBM Professor of Engineering and Applied Mathematics at Cornell and a recipient of the Turing Prize, the highest award in computer science. "My guess is that this particular framework is going to be applicable to a wide range of other problems," Hopcroft says. "It's a fundamentally new technique. When there's a breakthrough of that nature, usually, then, a subdiscipline forms, and in four or five years, a number of results come out." ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
