direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Fine-Grained Algorithm Design for Matching

Viatcheslav Korenwein (TU Berlin)


Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph problems. For m-edge and n-vertex graphs, it is well-known to be solvable in O(m√n) time; however, for several applications this running time is still too slow. Improving this worst-case upper bound resisted decades of research. In this talk we mainly focus on parameterizations of the input with respect to several kinds of distance to triviality, i.e. how far is the input from some linear-time solvable cases.

First, we demonstrate a linear-time fixed-parameter algorithm (with low polynomial parameter dependence) for various "distance to triviality"-parameters for the maximum matching problem. Second, we present linear time computable kernels of polynomial size.


Viatcheslav Korenwein
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras