Blar i Department of Informatics på forfatter "Sagunov, Danil"

Viser treff 1-6 av 6

    • 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 ...

    • 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 ...