Computer-assisted graph theory: a survey
Jorik Jooken
计算机和算法在图论中获得新结果方面发挥着日益重要的作用。在本综述中，我们介绍了计算机辅助图论中使用的广泛技术，包括在给定类别内详尽生成所有两两非同构图、使用包含图和不变量的可搜索数据库以及其他已建立和新兴的算法范式。我们涵盖了基于混合整数线性规划、半定规划、动态规划、SAT求解、元启发式和机器学习的方法。这些技术通过涵盖图论多个重要子领域的详细结果进行说明，如极值图论、图着色、结构图论、谱图论、正则图、拓扑图论、图中的特殊集合、代数图论和化学图论。我们还展示了一些较小的新结果，这些结果证明了在开发出适当工具后，计算机辅助图论方法可以多么容易地应用。
Computers and algorithms play an ever-increasing role in obtaining new results in graph theory. In this survey, we present a broad range of techniques used in computer-assisted graph theory, including the exhaustive generation of all pairwise non-isomorphic graphs within a given class, the use of searchable databases containing graphs and invariants as well as other established and emerging algorithmic paradigms. We cover approaches based on mixed integer linear programming, semidefinite program...
