Работа «The Weisfeiler-Leman Algorithm and Recognition of Graph Properties» за авторством Ильи Пономаренко и коллег Frank Fuhlbrück, Johannes Koebler и Oleg Verbitsky будет опубликована в трудах конференции 12th International Conference on Algorithms and Complexity, которая пройдет 10-12 мая 2021 года.
В работе предложен простой комбинаторный алгоритм, распознающий за полиномиальное время, является ли граф с простым числом вершин вершинно-транзитивным. Работа алгоритма состоит в применении двумерного алгоритма Вейсфейлера–Лемана к исходному графу и ко всем его вершинно-индивидуализированным копиям. Это первый пример использования алгоритма Вейсфейлера–Лемана для распознавания нетривиального свойства графа (в данном случае, вершинной транзитивности), а не изоморфизма графов.
Поздравляем авторов работы — Frank Fuhlbrück, Johannes Koebler, Ilia Ponomarenko и Oleg Verbitsky!
