T. Korhonen

activity

20192026

most citedGrid Induced Minor Theorem for Graphs of Small Degree

28 citations · 44 across the 32 of their papers we have counts for

collaborators

Showing 2020Show all

3 papers · 1 filter

cs.DS2020★ 1 cited

Listing Small Minimal Separators of a Graph

Tuukka Korhonen

Let $G$ be a graph and $a, b$ vertices of $G$ . A minimal $a, b$ -separator of $G$ is an inclusion-wise minimal vertex set of $G$ that separates $a$ and $b$ . We consider the problem of…

math.CO2020

Tight Bounds for Potential Maximal Cliques Parameterized by Vertex Cover

Tuukka Korhonen

We show that a graph with $n$ vertices and vertex cover of size $k$ has at most $4^{k} + n$ potential maximal cliques. We also show that for each positive integer $k$ , there exists a…

cs.DS2020★ 2 cited

SMS in PACE 2020

Tuukka Korhonen

We describe SMS, our submission to the exact treedepth track of PACE 2020. SMS computes the treedepth of a graph by branching on the small minimal separators of the graph.