论文标题
图形同构问题的最新进展
Recent Advances on the Graph Isomorphism Problem
论文作者
论文摘要
我们概述了图形同构问题的最新进展。我们的主要重点是Babai的准多态时间同构测试以及随后的发展，这些发展导致设计具有Quasi-PolyNomial参数化的运行时间，从$ n^{\ text {\ text {polylog}（k）（k）} $，其中$ k $是图形参数。第二个重点是组合Weisfeiler-Leman算法。
We give an overview of recent advances on the graph isomorphism problem. Our main focus will be on Babai's quasi-polynomial time isomorphism test and subsequent developments that led to the design of isomorphism algorithms with a quasi-polynomial parameterized running time of the from $n^{\text{polylog}(k)}$, where $k$ is a graph parameter such as the maximum degree. A second focus will be the combinatorial Weisfeiler-Leman algorithm.
