1 citations · 2 across the 4 of their papers we have counts for
5 papers
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…
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…
Fast FPT-Approximation of Branchwidth
Fedor V. Fomin, Tuukka Korhonen
Branchwidth determines how graphs, and more generally, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by speci…
Listing Small Minimal Separators of a Graph
Tuukka Korhonen
Let be a graph and vertices of . A minimal -separator of is an inclusion-wise minimal vertex set of that separates and . We consider the problem of…
Tight Bounds for Potential Maximal Cliques Parameterized by Vertex Cover
Tuukka Korhonen
We show that a graph with vertices and vertex cover of size has at most potential maximal cliques. We also show that for each positive integer , there exists a…