You may remember from your calculus classes that symmetry can sometimes be used to solve equations that at first look daunting. But some symmetries are so complicated that they are tough to spot, even for a computer. University of Michigan researchers recently reported a breakthrough in this area. From the release:
In less than a half-second, the new software captured 1083,687 different symmetries in an Internet connectivity graph of routers around the world. A symmetry in this graph signifies a way the routers could be shuffled that wouldn't change the operation.
Previous methods timed out in the 30 minutes they were given to generate results in these experiments. Darga said it would take these older programs days to solve such a complicated problem. In searching for symmetries in the road networks between cities and towns in Illinois, the new algorithm captured the 104,843 symmetries in less than a half-second, whereas the most robust previous algorithm took 16 minutes.
They are even giving the software away. You can request a copy here:
