1 citations · 2 across the 11 of their papers we have counts for
4 papers · 1 filter
Algorithmic Extensions of Dirac's Theorem
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
In 1952, Dirac proved the following theorem about long cycles in graphs with large minimum vertex degrees: Every -vertex -connected graph with minimum vertex degree $δ\ge…
Diverse Pairs of Matchings
Fedor V. Fomin, Petr A. Golovach, Lars Jaffke +2
We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph and an integer , ask whether has two (maximum/perfect) matchings w…
Maximizing Happiness in Graphs of Bounded Clique-Width
Ivan Bliznets, Danil Sagunov
Clique-width is one of the most important parameters that describes structural complexity of a graph. Probably, only treewidth is more studied graph width parameter. In this paper…
Building large k-cores from sparse graphs
Fedor V. Fomin, Danil Sagunov, Kirill Simonov
A popular model to measure network stability is the -core, that is the maximal induced subgraph in which every vertex has degree at least . For example, -cores are commonl…