66 citations · 206 across the 36 of their papers we have counts for
4 papers · 2 filters
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…