Year in review: New algorithm quickly spots identical networks | Science News



Support credible science journalism.

Subscribe to Science News today.


Year in review: New algorithm quickly spots identical networks

6:16am, December 15, 2015
Isomorphic graphs

SAME GRAPH, DIFFERENT SHAPE  These two graphs might look different, but each circle on the first graph corresponds to one on the second, connecting to the same other circles. Mathematicians call the graphs “isomorphic.” This year, computer scientist László Babai presented an algorithm that could overcome computers' longstanding difficulty in comparing such graphs. 

The fraternity of problems that confound computers has lost a prominent member. Computer scientist László Babai presented a new algorithm this year that efficiently tackles the graph isomorphism problem. It’s a type of problem that computers struggle to solve, even though a solution provided in advance is easily verified. Assuming it is confirmed, says Stanford theoretical computer scientist Ryan Williams, this is the biggest advance in the field in more than a decade.

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