Spezielle Matchings und Kantenfärbungen

• Antragsteller: Professor Dr. Dieter Rautenbach
• Fachliche Zuordnung: Theoretische Informatik ; Mathematik
• Förderung: Förderung von 2018 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 388217545

• Erstellungsjahr: 2021

Zusammenfassung der Projektergebnisse

In this project we investigated restricted matchings in graphs such as induced matchings, uniquely restricted matchings, and acyclic matchings. While the algorithmic problems related to general matchings are among the most famous efficiently solvable problems in discrete optimization, the corresponding problems for the mentioned restricted types of matchings are all hard. We managed to discover several beautiful results concerning the equality of different matching parameters and several tight lower bounds on the respective maximum sizes of the different matchings. Apart from these more structural results, we also provide efficient algorithms for restricted graph classes and several involved approximation algorithms.

Projektbezogene Publikationen (Auswahl)

• Approximating Maximum Uniquely Restricted Matchings in Bipartite Graphs, Discrete Appl. Math. 267 (2019), 30-40
  Baste, Julien; Rautenbach, Dieter & Sau, Ignasi
  
• Lower bounds on the uniquely restricted matching number, Graphs Combin. 35 (2019), 353-361
  Fürst, M. & Rautenbach, D.
  
• On some hard and some tractable cases of the maximum acyclic matching problem, Ann. Oper. Res. 279 (2019), 291-300
  Fürst, M. & Rautenbach, D.
  
• Uniquely restricted matchings in subcubic graphs, Discrete Appl. Math. 262 (2019), 189-194
  Fürst, Maximilian; Henning, Michael A. & Rautenbach, Dieter
  
• Approximating Maximum Acyclic Matchings by Greedy and Local Search Strategies, 26th International Conference on Computing and Combinatorics (COCOON 2020), Atlanta, USA, August 2020, Lecture Notes in Computer Science 12273 (2020), 542-553
  Baste, Julien; Fürst, Maximilian & Rautenbach, Dieter
  
• Low Weight Perfect Matchings, Electron. J. Comb. 2020
  Ehard, Stefan; Mohr, Elena & Rautenbach, Dieter
  
• On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs, Theor. Comput. Sci. 804 (2020), 126-138
  Fürst, M. & Rautenbach, D.
  
• Uniquely restricted matchings in subcubic graphs without short cycles, J. Graph Theory
  Fürst, M. & Rautenbach, D.