Zobrazeno 1 - 10
of 64
pro vyhledávání: '"Sagunov, Danil"'
The connection between Hamiltonicity and the independence numbers of graphs has been a fundamental aspect of Graph Theory since the seminal works of the 1960s. This paper presents a novel algorithmic perspective on these classical problems. Our contr
Externí odkaz:
http://arxiv.org/abs/2403.05943
According to the classic Chv{\'{a}}tal's Lemma from 1977, a graph of minimum degree $\delta(G)$ contains every tree on $\delta(G)+1$ vertices. Our main result is the following algorithmic "extension" of Chv\'{a}tal's Lemma: For any $n$-vertex graph $
Externí odkaz:
http://arxiv.org/abs/2310.09678
The fundamental theorem of Tur\'{a}n from Extremal Graph Theory determines the exact bound on the number of edges $t_r(n)$ in an $n$-vertex graph that does not contain a clique of size $r+1$. We establish an interesting link between Extremal Graph Th
Externí odkaz:
http://arxiv.org/abs/2307.07456
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 solution (above the guaran
Externí odkaz:
http://arxiv.org/abs/2305.02011
In 1959, Erd\H{o}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 time 2^{O(k)} n^{O(1)} decides whether a 2-connected n-vertex graph
Externí odkaz:
http://arxiv.org/abs/2202.03061
Autor:
Fomin, Fedor V., Golovach, Petr A., Lochet, William, Sagunov, Danil, Simonov, Kirill, Saurabh, Saket
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, the task is to decide whether
Externí odkaz:
http://arxiv.org/abs/2201.03318
Publikováno v:
In Theoretical Computer Science 12 April 2024 991
In 1952, Dirac proved the following theorem about long cycles in graphs with large minimum vertex degrees: Every $n$-vertex $2$-connected graph $G$ with minimum vertex degree $\delta\geq 2$ contains a cycle with at least $\min\{2\delta,n\}$ vertices.
Externí odkaz:
http://arxiv.org/abs/2011.03619
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 Pair of Matchings (
Externí odkaz:
http://arxiv.org/abs/2009.04567
Autor:
Bliznets, Ivan, Sagunov, Danil
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 we study how clique-width influences the complexity of the Maximum Hap
Externí odkaz:
http://arxiv.org/abs/2003.04605