47 citations · 678 across the 85 of their papers we have counts for
7 papers · 1 filter
Branch-width of represented matroids in matrix multiplication time
Mujin Choi, Tuukka Korhonen, Sang-il Oum
For an -element matroid given by an matrix representation over a finite field and an integer , we present an algorithm with running time $O_{k,\m…
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…
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Benjamin Bergougnoux, Vera Chekan, Robert Ganian +5
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simpl…
A polynomial kernel for -leaf power deletion
Jungho Ahn, Eduard Eiben, O-joung Kwon +1
For a non-negative integer , the -leaf power of a tree is a simple graph on the leaves of such that two vertices are adjacent in if and only if their di…
An FPT 2-Approximation for Tree-Cut Decomposition
Eunjung Kim, Sang-il Oum, Christophe Paul +2
The tree-cut width of a graph is a graph parameter defined by Wollan [J. Comb. Theory, Ser. B, 110:47-66, 2015] with the help of tree-cut decompositions. In certain cases, tree-cut…
The "art of trellis decoding" is fixed-parameter tractable
Jisu Jeong, Eun Jung Kim, Sang-il Oum
Given n subspaces of a finite-dimensional vector space over a fixed finite field , we wish to find a linear layout of the subspaces such that $\dim(…
Deciding first order logic properties of matroids
Tomas Gavenciak, Daniel Kral, Sang-il Oum
Frick and Grohe [J. ACM 48 (2006), 1184-1206] introduced a notion of graph classes with locally bounded tree-width and established that every first order logic property can be deci…