Improvements to classical graph theory have potential to impact modern-day problem solving
Friday, October 3, 2014 - 06:20
in Physics & Chemistry
In a reexamination of existing combinatorial optimization (graph) algorithms used to find the best solution with minimum enumeration, scientists from Simula Research Laboratory (Norway), University of Bergen (Norway), Purdue University, and Pacific Northwest National Laboratory explored the maximum bipartite matching problem. In the context of solving a system of linear equations, this problem resolves how to obtain the maximum number of nonzeros on the diagonal of a sparse matrix, where most entries are zero, by exchanging rows and columns of the original matrix (refer to Figure 1), which can improve runtimes, efficiency, and minimize errors.