28 citations · 44 across the 32 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
cs.DS2021★ 1 cited
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…
cs.DS2021
A Single-Exponential Time 2-Approximation Algorithm for Treewidth
Tuukka Korhonen
We give an algorithm that, given an -vertex graph and an integer , in time either outputs a tree decomposition of of width at most or determines…
cs.CC2021★ 1 cited
Lower Bounds on Dynamic Programming for Maximum Weight Independent Set
Tuukka Korhonen
We prove lower bounds on pure dynamic programming algorithms for maximum weight independent set (MWIS). We model such algorithms as tropical circuits, i.e., circuits that compute w…