Combinatorial structures and algorithms in symmetric graphs

对称图中的组合结构和算法

• 批准号: 413902284
• 负责人: Professor Dr. Martin Skutella, since 9/2019
• 金额: --
• 依托单位: Department of Computer Science
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2018
• 资助国家: 德国
• 起止时间: 2017-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/413902284?language=en
• 关键词: Combinatorial; structures; algorithms; symmetric; graphs

The main goal of this project is to derive new theoretical results about cycles and other fundamental structures such as paths and matchings in various families of highly symmetric graphs, and to implement the corresponding combinatorial algorithms. The starting point of our project is a famous conjecture due to Lovász from the 1970s, which asserts that every connected and vertex-transitive graph has a Hamilton cycle, apart from five known exceptions. A vertex-transitive graph is a graph that ‘looks the same’ from the point of view of any vertex, and a Hamilton cycle is a cycle that visits every vertex exactly once. One of the goals of this project is to tackle several special cases of Lovász’ conjecture that are also long-standing problems, and for which we recently made significant progress. This part of the project is a continuation of our earlier solutions of multiple long-standing problems in this area, including the notorious middle levels conjecture from the 1980s. Moreover, we will also develop new Gray code algorithms for different combinatorial objects of interest for computer scientists, such as bitstrings, permutations, geometric configurations, posets and polytopes. Solving these problems requires to combine and develop new theoretical tools and techniques from different subareas, and these new techniques and connections will be of interest for other researchers. We also plan to implement all the algorithms developed in the course of this project, and to make them available for other researchers, students and educators. For this purpose, jointly with other researchers, we will relaunch the Combinatorial Object Server, a website first established by Frank Ruskey. This website provides an easy-to-use interface to run, explore and download open-source code for various fundamental combinatorial algorithms.

该项目的主要目标是在各种高度对称图族中获得关于圈和其他基本结构（如路径和匹配）的新理论结果，并实现相应的组合算法。我们项目的起点是20世纪70年代由Lovász提出的一个著名猜想，该猜想断言，除了五个已知的例外，每个连通的顶点传递图都有一个汉密尔顿圈。顶点传递图是从任何顶点的角度看“看起来相同”的图，而汉密尔顿圈是访问每个顶点仅一次的圈。该项目的目标之一是解决Lovász猜想的几个特殊情况，这些情况也是长期存在的问题，我们最近取得了重大进展。该项目的这一部分是我们早期解决该领域多个长期存在的问题的延续，包括20世纪80年代臭名昭着的中层猜想。此外，我们还将为计算机科学家感兴趣的不同组合对象开发新的格雷码算法，如位串，排列，几何配置，偏序集和多面体。解决这些问题需要联合收割机，并从不同的子领域开发新的理论工具和技术，这些新的技术和连接将是其他研究人员感兴趣的。我们还计划实施在该项目过程中开发的所有算法，并将其提供给其他研究人员，学生和教育工作者。为此，我们将与其他研究人员一起重新启动组合对象服务器，这是一个由Frank Ruskey首先建立的网站。该网站提供了一个易于使用的界面，用于运行、探索和下载各种基本组合算法的开源代码。