28 citations · 44 across the 32 of their papers we have counts for
8 papers · 1 filter
Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
Tuukka Korhonen
We present time algorithms for various problems about decomposing a given undirected graph by edge cuts or vertex separators of size into parts that are ``well-…
Packing Short Cycles
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +6
Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of v…
Fixed-Parameter Tractability of Hedge Cut
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +2
In the Hedge Cut problem, the edges of a graph are partitioned into groups called hedges, and the question is what is the minimum number of hedges to delete to disconnect the graph…
Unavoidable induced subgraphs in graphs with complete bipartite induced minors
Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen +2
We prove that if a graph contains the complete bipartite graph as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. W…
Stability in Graphs with Matroid Constraints
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +1
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…
Minor Containment and Disjoint Paths in almost-linear time
Tuukka Korhonen, Michał Pilipczuk, Giannos Stamoulis
We give an algorithm that, given graphs and , tests whether is a minor of in time ; here, is the number of vertices of and the ${\cal…
Structural perspective on constraint-based learning of Markov networks
Tuukka Korhonen, Fedor V. Fomin, Pekka Parviainen
Markov networks are probabilistic graphical models that employ undirected graphs to depict conditional independence relationships among variables. Our focus lies in constraint-base…
Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
Tuukka Korhonen, Marek Sokołowski
We give an algorithm that given a graph with vertices and edges and an integer , in time either outputs a rank decomposition of of width…