8 papers
Longest Cycle above Erdős-Gallai Bound
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G)\geq 2 contains a cycle of length at least ad(G). We provide an algorithm that for k\geq 0 in ti…
Detours in Directed Graphs
Fedor V. Fomin, Petr A. Golovach, William Lochet +3
We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Pa…
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…
On Happy Colorings, Cuts, and Structural Parameterizations
Ivan Bliznets, Danil Sagunov
We study the Maximum Happy Vertices and Maximum Happy Edges problems. The former problem is a variant of clusterization, where some vertices have already been assigned to clusters.…