Combining Connectivity Theory and Algorithms with Maximum Adjacency Orderings

点击翻译按钮获取中文摘要

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.