1 citations · 2 across the 11 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.DS2022
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…
cs.DS2022
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…