Blog: A New Kind of Counting; Graph Coloring Problem solution

A New Kind of Counting
Max Planck Society (02/06/09) Abrell, Barbara

Scientists at Germany's Max Planck Institute for Dynamics and Self-Organization (MPIDS) and Cornell University have developed a computer algorithm to crack previously unsolvable counting problems. Such counting problems are visualized by researchers as a network of lines and nodes, which means only one basic challenge must be met: Determining the number of different ways to color in the nodes with a certain number of colors without assigning the same color to nodes joined by a line. A node's color is imbued with a completely new significance, depending on the application. "The existing algorithm copies the whole network for each stage of the calculation and only changes one aspect of it each time," says MPIDS scientist Frank van Bussel. The researchers move through the network on a node-by-node basis, and the program never looks at the entire network but only at the next node point. At the first node point, the program cannot finalize the color selection as it would have to know how all the other nodes are linked to each other. Instead, the program notes down a formula for the first lattice point, which contains this uncertainty as an unknown quantity. As the program moves through the network, all the connections are exposed and the unknown quantities are removed. The program's knowledge of the network is complete once it has reached the final node point. The calculation time for a square lattice the size of a chess board is estimated to be many billions of years, but Denny Fliegner of MPIDS says the program can accomplish this in just seven seconds.

View Full Article