Maximilian Fürst

collaborators

2 papers

math.CO2017

On some Graphs with a Unique Perfect Matching

S. Chaplick, M. Fürst, F. Maffray +1

We show that deciding whether a given graph $G$ of size $m$ has a unique perfect matching as well as finding that matching, if it exists, can be done in time $O (m)$ if $G$ is eithe…

math.CO2017

Locally Searching for Large Induced Matchings

Maximilian Fürst, Marilena Leichter, Dieter Rautenbach

It is an easy observation that a natural greedy approach yields a $(d - O (1))$ -factor approximation algorithm for the maximum induced matching problem in $d$ -regular graph…