Combining Connectivity Theory and Algorithms with Maximum Adjacency Orderings

将连通性理论和算法与最大邻接顺序相结合

• 批准号: 270450205
• 负责人: Professor Dr. Jens M. Schmidt
• 金额: --
• 依托单位: Lehrstuhl für Algorithmen und Komplexität
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2015
• 资助国家: 德国
• 起止时间: 2014-12-31 至 2018-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/270450205?language=en
• 关键词: Combining; Connectivity; Theory; Algorithms; Maximum

A fundamental parameter of a graph is its connectivity: If we visualize the graph as road network, the connectivity asks for the maximal number of disjoint paths between each pair of cities.There is a plethora of algorithms in theoretical computer science that compute the connectivity of a graph. Traditionally, most of them use flow networks. However, in the last years a different method has become increasingly more important, as it does not need to use flow networks: The application of Maximal Adjacency Orderings. Interestingly, these allow to deduce several classic results from structural graph theory not only in a much simpler way than the original proofs but also generalize them. Connections like these to discrete mathematics have proven to be very profitable for both worlds, graph theory and theoretical computer science, in the past.This project aims at studying graph-theoretical connectivity properties of Maximum Adjacency Orderings as well as their applications to more efficient and simpler algorithms for connectivity.

图的一个基本参数是它的连通性：如果我们将图可视化为道路网络，则连通性要求每对城市之间有最大数量的不相交路径。理论计算机科学中有大量的算法来计算图的连通性。传统上，它们中的大多数使用流网络。然而，在过去的几年中，一种不同的方法变得越来越重要，因为它不需要使用流网络：最大邻接排序的应用。有趣的是，这些允许从结构图论中推导出几个经典的结果，不仅比原始证明简单得多，而且还推广了它们。像这样的离散数学的连接已经被证明是非常有利可图的两个世界，图论和理论计算机科学，在过去。这个项目旨在研究最大邻接序的图论连通性特性，以及它们的应用更有效和更简单的算法的连通性。