Zobrazeno 1 - 10
of 61
pro vyhledávání: '"Korhonen, Tuukka"'
Autor:
Chudnovsky, Maria, Hatzel, Meike, Korhonen, Tuukka, Trotignon, Nicolas, Wiederrecht, Sebastian
We prove that if a graph contains the complete bipartite graph $K_{134, 12}$ as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. With a longer and more technical proof, we prove that if a graph contai
Externí odkaz:
http://arxiv.org/abs/2405.01879
We study the following Independent Stable Set problem. Let G be an undirected graph and M = (V(G),I) be a matroid whose elements are the vertices of G. For an integer k\geq 1, the task is to decide whether G contains a set S\subseteq V(G) of size at
Externí odkaz:
http://arxiv.org/abs/2404.03979
We give an algorithm that, given graphs $G$ and $H$, tests whether $H$ is a minor of $G$ in time ${\cal O}_H(n^{1+o(1)})$; here, $n$ is the number of vertices of $G$ and the ${\cal O}_H(\cdot)$-notation hides factors that depend on $H$ and are comput
Externí odkaz:
http://arxiv.org/abs/2404.03958
Markov networks are probabilistic graphical models that employ undirected graphs to depict conditional independence relationships among variables. Our focus lies in constraint-based structure learning, which entails learning the undirected graph from
Externí odkaz:
http://arxiv.org/abs/2403.08562
Autor:
Korhonen, Tuukka, Sokołowski, Marek
We give an algorithm that given a graph $G$ with $n$ vertices and $m$ edges and an integer $k$, in time $O_k(n^{1+o(1)}) + O(m)$ either outputs a rank decomposition of $G$ of width at most $k$ or determines that the rankwidth of $G$ is larger than $k
Externí odkaz:
http://arxiv.org/abs/2402.12364
A graph $G$ contains a graph $H$ as an induced minor if $H$ can be obtained from $G$ after vertex deletions and edge contractions. We show that for every $k$-vertex planar graph $H$, every graph $G$ excluding $H$ as an induced minor and $K_{t,t}$ as
Externí odkaz:
http://arxiv.org/abs/2312.07962
The classic technique of Baker [J. ACM '94] is the most fundamental approach for designing approximation schemes on planar, or more generally topologically-constrained graphs, and it has been applied in a myriad of different variants and settings thr
Externí odkaz:
http://arxiv.org/abs/2310.20623
Let $A$ and $B$ be sets of vertices in a graph $G$. Menger's theorem states that for every positive integer $k$, either there exists a collection of $k$ vertex-disjoint paths between $A$ and $B$, or $A$ can be separated from $B$ by a set of at most $
Externí odkaz:
http://arxiv.org/abs/2309.08169
Autor:
Korhonen, Tuukka, Järvisalo, Matti
We describe SharpSAT-TD, our submission to the unweighted and weighted tracks of the Model Counting Competition in 2021-2023, which has won in total $6$ first places in different tracks of the competition. SharpSAT-TD is based on SharpSAT [Thurley, S
Externí odkaz:
http://arxiv.org/abs/2308.15819
Autor:
Korhonen, Tuukka, Lokshtanov, Daniel
A graph $G$ contains a graph $H$ as an induced minor if $H$ can be obtained from $G$ by vertex deletions and edge contractions. The class of $H$-induced-minor-free graphs generalizes the class of $H$-minor-free graphs, but unlike $H$-minor-free graph
Externí odkaz:
http://arxiv.org/abs/2308.04795