Создан алгоритм, анализирующий симметрию графов

Ученые из Университета штата Мичиган разработали алгоритм, существенно сокращающий время, необходимое для анализа симметрии графов.

Алгоритм, реализованный в программе с открытым исходным кодом, основан на программе "saucy", разработанной в 2004 г. этой же исследовательской группой, сообщает пресс-служба университета. По мнению разработчиков, существующие аналогичные инструменты, такие как "nauty", "saucy" и "bliss" требуют затрат квадратичного времени и неэффективны, если необходимо произвести анализ больших и разреженных графов. Новый же алгоритм лишен этих недостатков.

За менее чем полсекунды новое программное обеспечение находит более 1 млн видов симметрий в графе, описывающем интернет.