66 citations · 206 across the 36 of their papers we have counts for
5 papers · 1 filter
A Linear Vertex Kernel for Maximum Internal Spanning Tree
Fedor V. Fomin, Serge Gaspers, Saket Saurabh +1
We present a polynomial time algorithm that for any graph G and integer k >= 0, either finds a spanning tree with at least k internal vertices, or outputs a new graph G' on at most…
Kernels for Feedback Arc Set In Tournaments
Stéphane Bessy, Fedor V. Fomin, Serge Gaspers +4
A tournament T=(V,A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the Fe…
A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
Serge Gaspers, Gregory B. Sorkin
In this paper we introduce "hybrid" Max 2-CSP formulas consisting of "simple clauses", namely conjunctions and disjunctions of pairs of variables, and general 2-variable clauses, w…
An Exponential Time 2-Approximation Algorithm for Bandwidth
Martin Fürer, Serge Gaspers, Shiva Prasad Kasiviswanathan
The bandwidth of a graph G on n vertices is the minimum b such that the vertices of G can be labeled from 1 to n such that the labels of every pair of adjacent vertices differ by a…
Feedback Vertex Sets in Tournaments
Serge Gaspers, Matthias Mnich
We study combinatorial and algorithmic questions around minimal feedback vertex sets in tournament graphs. On the combinatorial side, we derive strong upper and lower bounds on the…