Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Tuesday, May 09, 2023, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Sebastian Haslebacher

Exact Matching: Characterization on Restricted Graph Classes

Given an integer k and a simple graph G with edges colored red or blue, Exact Matching (EM) is the problem of deciding whether G has a perfect matching containing exactly k red edges. While a randomized polynomial-time algorithm for EM has been known since the 1980s, the best deterministic algorithm to date takes exponential time. However, better deterministic algorithms are known for several restricted graph classes. We extend this line of work with a new characterization of the exact matchings in unit-interval graphs, chain graphs, and complete r-partite graphs. This characterization implies deterministic polynomial-time algorithms on these graph classes. These results are from my master's thesis supervised by Bernd Gärtner and Nicolas El Maalouly.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login