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)

• Uniquely restricted matchings in subcubic graphs without short cycles, J. Graph Theory
  M. Fürst and D. Rautenbach
  (Siehe online unter https://doi.org/10.1002/jgt.22632)
• Approximating Maximum Uniquely Restricted Matchings in Bipartite Graphs, Discrete Appl. Math. 267 (2019), 30-40
  J. Baste, D. Rautenbach, and I. Sau
  (Siehe online unter https://doi.org/10.1016/j.dam.2019.04.024)
• Lower bounds on the uniquely restricted matching number, Graphs Combin. 35 (2019), 353-361
  M. Fürst and D. Rautenbach
  (Siehe online unter https://doi.org/10.1007/s00373-018-1991-8)
• On some hard and some tractable cases of the maximum acyclic matching problem, Ann. Oper. Res. 279 (2019), 291-300
  M. Fürst and D. Rautenbach
  (Siehe online unter https://doi.org/10.1007/s10479-019-03311-1)
• Uniquely restricted matchings in subcubic graphs, Discrete Appl. Math. 262 (2019), 189-194
  M. Fürst. M.A. Henning, and D. Rautenbach
  (Siehe online unter https://doi.org/10.1016/j.dam.2019.02.013)
• 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
  J. Baste, M. Fürst and D. Rautenbach
  (Siehe online unter https://doi.org/10.1007/978-3-030-58150-3_44)
• Low Weight Perfect Matchings, Electron. J. Comb. 2020
  S. Ehard, E. Mohr and D. Rautenbach
  (Siehe online unter https://doi.org/10.37236/9994)
• On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs, Theor. Comput. Sci. 804 (2020), 126-138
  M. Fürst and D. Rautenbach
  (Siehe online unter https://doi.org/10.1016/j.tcs.2019.11.020)