58 citations · 239 across the 47 of their papers we have counts for
5 papers · 2 filters
Towards a Parameterized Approximation Dichotomy of MinCSP for Linear Equations over Finite Commutative Rings
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
We consider the MIN-r-LIN(R) problem: given a system S of length-r linear equations over a ring R, find a subset of equations Z of minimum cardinality such that S-Z is satisfiable.…
Exact Algorithms for Clustered Planarity with Linear Saturators
Giordano Da Lozzo, Robert Ganian, Siddharth Gupta +3
We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an -vertex planar graph whose vertices are partitioned into independent sets (called clus…
From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
Eduard Eiben, Robert Ganian, Iyad Kanj +2
Several works have recently investigated the parameterized complexity of data completion problems, motivated by their applications in machine learning, and clustering in particular…
A Tight Subexponential-time Algorithm for Two-Page Book Embedding
Robert Ganian, Haiko Mueller, Sebastian Ordyniak +2
A book embedding of a graph is a drawing that maps vertices onto a line and edges to simple pairwise non-crossing curves drawn into pages, which are half-planes bounded by that lin…
Algorithms and Complexity of Difference Logic
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +1
Difference Logic (DL) is a fragment of linear arithmetics where atoms are constraints x+k <= y for variables x,y (ranging over Q or Z) and integer k. We study the complexity of dec…