From the 2 of 13 linked papers with an AI index.
13 papers
Courcelle's Theorem in Truly Linear FPT
Tuukka Korhonen, Daniel Lokshtanov, Saket Saurabh
The paper develops a general technique for obtaining truly linear fixed‑parameter tractable (TLFPT) algorithms when parameterized by treewidth, providing a TLFPT version of Courcel…
Branch-width of represented matroids in matrix multiplication time
Mujin Choi, Tuukka Korhonen, Sang-il Oum
The paper presents an algorithm that computes a branch-decomposition of a matroid given by a matrix representation in time essentially O(n^ω), improving on previous cubic-time meth…
Connectivity augmentation is fixed-parameter tractable
Tuukka Korhonen, Mikkel Thorup
In the vertex connectivity augmentation problem, we are given an undirected -vertex graph , a set of links , and integers and…
Branch-width of connectivity functions is fixed-parameter tractable
Tuukka Korhonen, Sang-il Oum
A connectivity function on a finite set is a symmetric submodular function with . We prove that finding a branch-decomposition of…
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-…