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


Science News is a nonprofit.

Support us by subscribing now.


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.

The problem requires computers to compare two graphs, or networks of connected points, and determine whether all points are linked in the same way. Previously, the time required to solve the problem rose nearly exponentially with graph size. Babai’s algorithm, born from decades of mathematical effort, keeps the required computing time

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 on 2015 Top 25

From the Nature Index Paid Content