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

Matchings in Graphen gehören zu den grundlegendsten und am besten untersuchten Objekten der kombinatorischen Optimierung. Ihre Betrachtung führte zu einigen der klassischsten Konzepte, Resultate und Algorithmen in diesem Gebiet. Mehrere eingeschränkte Typen von Matchings sind vorgeschlagen worden. In diesem Projekt möchten wir Fragen über induzierte Matchings, uniquely restricted Matchings und degenerierte Matchings sowie die zugehörigen Kantenfärbungen angehen. Unser Fokus liegt auf strukturellen Ergebnissen, Schranken und exakten sowie approximativen Algorithmen.

• DFG-Verfahren: Sachbeihilfen