Combining Connectivity Theory and Algorithms with Maximum Adjacency Orderings

• Applicant: Professor Dr. Jens M. Schmidt
• Subject Area: Theoretical Computer Science
• Term: from 2015 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 270450205

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.

• DFG Programme: Research Grants