New algorithm cracks graph problem | Science News

Be a Champion for Science

Get your subscription to

Science News when you join.


News

New algorithm cracks graph problem

Computer science ‘advance of decade’ helps identify identical networks

By
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.

This article is available only to subscribing members. Join the Society today or Log in.

Get Science News headlines by e-mail.

More from Science News