3 citations · 3 across the 4 of their papers we have counts for
5 papers · 1 filter
Fault-Tolerant Edge-Disjoint Paths -- Beyond Uniform Faults
David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler +1
The overwhelming majority of survivable (fault-tolerant) network design models assume a uniform fault model. Such a model assumes that every subset of the network resources (edges…
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…
Fast Algorithms for Delta-Separated Sparsity Projection
Henning Bruhn, Oliver Schaudt
We describe a fast approximation algorithm for the -separated sparsity projection problem. The -separated sparsity model was introduced by Hegde, Duarte and Cevher (2009) to…
Recognizing k-equistable graphs in FPT time
Eun Jung Kim, Martin Milanic, Oliver Schaudt
A graph is called equistable if there exist a positive integer and a weight function such that is a maximal stable set of …