3 citations · 3 across the 4 of their papers we have counts for
3 papers · 1 filter
Improved approximation algorithms for hitting 3-vertex paths
Samuel Fiorini, Gwenaël Joret, Oliver Schaudt
We study the problem of deleting a minimum cost set of vertices from a given vertex-weighted graph in such a way that the resulting graph has no induced path on three vertices. Thi…
How to Secure Matchings Against Edge Failures
Felix Hommelsheim, Moritz Mühlenthaler, Oliver Schaudt
Suppose we are given a bipartite graph that admits a perfect matching and an adversary may delete any edge from the graph with the intention of destroying all perfect matchings. We…
Erdős-Pósa property for labelled minors: 2-connected minors
Henning Bruhn, Felix Joos, Oliver Schaudt
In the 1960s, Erdős and Pósa proved that there is a packing-covering duality for cycles in graphs. As part of the graph minor project, Robertson and Seymour greatly extended this:…