New algorithm cracks graph problem
Computer science ‘advance of decade’ helps identify identical networks
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.
Jeremy Kun
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
