Showing 2019Show all
3 papers · 1 filter
math.CO2019
A Polynomial Kernel for Paw-Free Editing
Eduard Eiben, William Lochet, Saket Saurabh
For a fixed graph , the -free-editing problem asks whether we can modify a given graph by adding or deleting at most edges such that the resulting graph does not cont…
cs.DS2019
The Parameterized Complexity of Clustering Incomplete Data
Eduard Eiben, Robert Ganian, Iyad Kanj +2
We study fundamental clustering problems for incomplete data. Specifically, given a set of incomplete d-dimensional vectors (representing rows of a matrix), the goal is to complete…
cs.DS2019
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
Eduard Eiben, Robert Ganian, Thekla Hamm +1
We develop a framework for applying treewidth-based dynamic programming on graphs with "hybrid structure", i.e., with parts that may not have small treewidth but instead possess ot…