1 citations · 2 across the 11 of their papers we have counts for
3 papers · 1 filter
Tree Containment Above Minimum Degree is FPT
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
According to the classic Chv{á}tal's Lemma from 1977, a graph of minimum degree contains every tree on vertices. Our main result is the following algorithmic "exten…
Turán's Theorem Through Algorithmic Lens
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
The fundamental theorem of Turán from Extremal Graph Theory determines the exact bound on the number of edges in an -vertex graph that does not contain a clique of size…
Approximating Long Cycle Above Dirac's Guarantee
Fedor F. Fomin, Petr A. Golovach, Danil Sagunov +1
Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit ``natural'' guarantees bringin…