28 citations · 44 across the 32 of their papers we have counts for
4 papers · 1 filter
Separator Theorem for Minor-Free Graphs in Linear Time
Édouard Bonnet, Tuukka Korhonen, Hung Le +2
The planar separator theorem by Lipton and Tarjan [FOCS '77, SIAM Journal on Applied Mathematics '79] states that any planar graph with vertices has a balanced separator of siz…
Dynamic Meta-Kernelization
Christian Bertram, Deborah Haun, Mads Vestergaard Jensen +1
Kernelization studies polynomial-time preprocessing algorithms. Over the last 20 years, the most celebrated positive results of the field have been linear kernels for classical NP-…
Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
Hans L. Bodlaender, Fedor V. Fomin, Tuukka Korhonen
The induced matching width of a tree decomposition of a graph is the cardinality of a largest induced matching of , such that there exists a bag that intersects every ed…
Dynamic Treewidth in Logarithmic Time
Tuukka Korhonen
We present a dynamic data structure that maintains a tree decomposition of width at most of a dynamic graph with treewidth at most , which is updated by edge insertions a…