New algorithm cracks graph problem | Science News



Help us keep you informed.

Support Science News.


New algorithm cracks graph problem

Computer science ‘advance of decade’ helps identify identical networks

4:53pm, November 11, 2015
 László Babai

YOU FOLLOW?  László Babai describes his new algorithm at the University of Chicago on November 10. The algorithm solves the tricky graph isomorphism problem faster than ever before.

A puzzle that has long flummoxed computers and the scientists who program them has suddenly become far more manageable.

A new algorithm efficiently solves the graph isomorphism problem, computer scientist László Babai announced November 10 at a Combinatorics and Theoretical Computer Science seminar at the University of Chicago. The problem requires determining whether two separate sets of interconnected points, known as graphs, are linked in the same way even if the graphs look very different. In practice, existing algorithms can do the job in reasonable time, but it was possible that extremely complex graphs would make the problem intractable. Not anymore.

“My first thought was that this was a joke. I checked the month to make sure it wasn’t April,” says Ryan Williams, a Stanford University computer scientist. “It’s a huge jump in our understanding of the problem.” He

This article is only available to Science News subscribers. Already a subscriber? Log in now. Or subscribe today for full access.

Get Science News headlines by e-mail.

More from Science News

From the Nature Index Paid Content