The Graph Isomorphism Problem (Dagstuhl Seminar 15511)
The Graph Isomorphism Problem (Dagstuhl Seminar 15511)
复制标题
DOI：
10.4230/dagrep.5.12.1
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
L. Babai;A. Dawar;Pascal Schweitzer;J. Torán
中科院分区：
文献类型：
--
作者：
L. Babai;A. Dawar;Pascal Schweitzer;J. Torán
本报告记录了Dagstuhl研讨会15511“图同构问题”的程序和结果。研讨会的目的是汇集研究人员在许多主题密切相关的同构问题，以促进他们的合作。为此，与会者的研讨会包括研究人员工作的理论和实践方面的同构范围从领域的算法组理论，有限模型理论，组合优化算法。会议的一个亮点是提出了一个新的图同构问题的准多项式时间算法，这是自1983年以来的第一次改进。
This report documents the program and the outcomes of Dagstuhl Seminar 15511 "The Graph Isomorphism Problem". The goal of the seminar was to bring together researchers working on the numerous topics closely related to the Isomorphism Problem to foster their collaboration. To this end the participants of the seminar included researchers working on the theoretical and practical aspects of isomorphism ranging from the fields of algorithmic group theory, finite model theory, combinatorial optimization to algorithmics. A highlight of the conference was the presentation of a new quasi-polynomial time algorithm for the Graph Isomorphism Problem, providing the first improvement since 1983.