24 citations · 124 across the 75 of their papers we have counts for
6 papers · 1 filter
SAT-Encodings for Treecut Width and Treedepth
Robert Ganian, Neha Lodha, Sebastian Ordyniak +1
In this paper we propose, implement, and test the first practical decomposition algorithms for the width parameters treecut width and treedepth. These two parameters have recently…
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…
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…
Parameterized Algorithms for Book Embedding Problems
Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani +1
A k-page book embedding of a graph G draws the vertices of G on a line and the edges on k half-planes (called pages) bounded by this line, such that no two edges on the same page c…
On Strict (Outer-)Confluent Graphs
Henry Förster, Robert Ganian, Fabian Klute +1
A strict confluent (SC) graph drawing is a drawing of a graph with vertices as points in the plane, where vertex adjacencies are represented not by individual curves but rather by…
A Join-Based Hybrid Parameter for Constraint Satisfaction
Robert Ganian, Sebastian Ordyniak, Stefan Szeider
We propose joinwidth, a new complexity parameter for the Constraint Satisfaction Problem (CSP). The definition of joinwidth is based on the arrangement of basic operations on relat…