FROM GRAPH THEORY TO MATROIDS: ALGORITHMIC ISSUES AND APPLICATIONS

Abstract: 

This project lies in the intersection of two of the most active and rich in deep problems areas in Discrete Mathematics, namely Graph Theory and Matroid Theory.

There are four main axes of proposed research, as reflected by the four research teams in this project, which range from the theoretical to the algorithmic.

  1. Starting from the matroids, we propose to develop a decomposition theory for signed graphic matroids as well as recognition algorithms for the aforementioned class that will provide the means for answering some of the most important questions in this field.
  2. Next we propose to examine important algorithmic consequences of the much celebrated Graph Minor Theory of Robertson and Seymour, by extending the techniques so developed to other areas and problems, and even more importantly by further enhancing them.
  3. In the third axis of research our goal is to develop the first detailed polyhedral analysis of matroid intersection, thereby providing a general solid mathematical framework for the majority of discrete optimization problems, and also a polyhedral description for the most important structural theorems in matroid theory.
  4. Finally efficient exact solution algorithms will be developed and implemented using the aforementioned theoretical results, for a plethora of integer programming problems.

This research proposal possesses the rare characteristic of being both theoretical and applied, in the sense that the problems which proposes to solve have both a deep theoretical and applied impact. The theoretical impact will be due to the settling of various conjectures in the field as well as by providing deep structural results, while these results will also foster the development of a number of algorithms for various important combinatorial problems.

Project info

Acronym:
GTM
Coordinating Institution:
Aristotle University of Thessaloniki
Scientific Coordinator:
Pitsoulis Leonidas
Research Team 2 Leader:
Thilikos Dimitrios
Research Team 3 Leader:
Mourtos Ioannis
Research Team 4 Leader:
Magos Dimitrios

Stats

I.D.:
617
Mis:
379437
Duration (months):
43
Budget:
599 955.00
Diavgeia:
ΑΔΑ: Β4Λ59-ΦΔΞ

Document Library

News