New algorithm cracks graph problem | Science News

ADVERTISEMENT

MISSION CRITICAL

Support credible science journalism.

Subscribe to Science News today.


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

From the Nature Index Paid Content