Browsing Bergen Open Research Archive by Author "Sagunov, Danil"

Now showing items 1-9 of 9

    • Approximating Long Cycle Above Dirac's Guarantee 

      Fomin, Fedor; Golovach, Petr; Simonov, Kirill; Sagunov, Danil (Journal article; Peer reviewed, 2023)
      Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit "natural" guarantees bringing to algorithmic questions whether a better ...

    • Building large k-cores from sparse graphs 

      Fomin, Fedor; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2020)
      A popular model to measure network stability is the k-core, that is the maximal induced subgraph in which every vertex has degree at least k. For example, k-cores are commonly used to model the unraveling phenomena in ...

    • Building large k-cores from sparse graphs 

      Fomin, Fedor; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2023)
      A k-core of a graph G is the maximal induced subgraph in which every vertex has degree at least k. In the Edge k-Core optimization problem, we are given a graph G and integers k, b and p. The task is to ensure that the ...

    • Detours in Directed Graphs 

      Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Sagunov, Danil; Simonov, Kirill; Saurabh, Saket (Journal article; Peer reviewed, 2022)
      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 Path that we study, called Longest Detour, ...

    • Detours in directed graphs 

      Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Sagunov, Danil; Saurabh, Saket; Simonov, Kirill (Journal article; Peer reviewed, 2023)
      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 Path that we study, called Longest Detour, ...

    • Diverse Pairs of Matchings 

      Fomin, Fedor; Golovach, Petr; Jaffke, Lars; Philip, Geevarghese; Sagunov, Danil (Journal article; Peer reviewed, 2020)
      We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse ...

    • Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms 

      Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2022)
      We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree ...

    • Longest Cycle Above Erdös-Gallai Bound 

      Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2022)
      In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2^𝒪(k)⋅n^𝒪(1) decides whether a 2-connected ...

    • Turán's Theorem Through Algorithmic Lens 

      Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2023)