Fedor V. Fomin

activity

20232026

most citedTight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths

1 citations · 2 across the 20 of their papers we have counts for

collaborators

Showing 2023Show all

2 papers · 1 filter

cs.DS2023

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 $δ (G)$ contains every tree on $δ (G) + 1$ vertices. Our main result is the following algorithmic "exten…

cs.DS2023

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…