- Mathematical Center in Akademgorodok
- Scientist of the Mathematical Center in Akademgorodok Ilia Ponomarenko was awarded Springer's Best paper award
Scientist of the Mathematical Center in Akademgorodok Ilia Ponomarenko was awarded Springer's Best paper award
The paper "The Weisfeiler-Leman Algorithm and Recognition of Graph Properties" by Ilia Ponomarenko and colleagues Frank Fuhlbrück, Johannes Koebler and Oleg Verbitsky will be published in the proceedings of the 12th International Conference on Algorithms and Complexity, which will take place on May 10–12, 2021.
The paper proposes a simple combinatorial algorithm that in polynomial time recognizes whether a graph with a prime number of vertices is vertex-transitive. The work of the algorithm consists of applying the two-dimensional Weisfeiler-Lehmann algorithm to the original graph and to all its vertex-individualized copies. This is the first example of using the Weisfeiler-Lehmann algorithm to recognize a non-trivial property of a graph (in this case, vertex transitivity) rather than the isomorphism of graphs.
Congratulations to the authors of the work — Frank Fuhlbrück, Johannes Koebler, Ilia Ponomarenko and Oleg Verbitsky!