28 citations · 44 across the 32 of their papers we have counts for
6 papers · 1 filter
Shortest Cycles With Monotone Submodular Costs
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +2
We introduce the following submodular generalization of the Shortest Cycle problem. For a nonnegative monotone submodular cost function defined on the edges (or the vertices) o…
An Improved Parameterized Algorithm for Treewidth
Tuukka Korhonen, Daniel Lokshtanov
We give an algorithm that takes as input an -vertex graph and an integer , runs in time , and outputs a tree decomposition of of width at most $k…
Tight Lower Bounds for Problems Parameterized by Rank-width
Benjamin Bergougnoux, Tuukka Korhonen, Jesper Nederlof
We show that there is no time algorithm for Independent Set on -vertex graphs with rank-width , unless the Exponential Time Hypothesis (ETH) fails. Our…
Fixed-Parameter Tractability of Maximum Colored Path and Beyond
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +2
We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the…
Computing Tree Decompositions with Small Independence Number
Clément Dallard, Fedor V. Fomin, Petr A. Golovach +2
The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the mini…
Grid Induced Minor Theorem for Graphs of Small Degree
Tuukka Korhonen
A graph is an induced minor of a graph if can be obtained from by vertex deletions and edge contractions. We show that there is a function $f(k, d) = O(k^{10} + 2^{…