6 citations · 16 across the 12 of their papers we have counts for
5 papers · 1 filter
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…
Threshold Treewidth and Hypertree Width
Andre Schidler, Robert Ganian, Manuel Sorge +1
Treewidth and hypertree width have proven to be highly successful structural parameters in the context of the Constraint Satisfaction Problem (CSP). When either of these parameters…
Testing Upward Planarity of Partial -Trees
Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati +3
We present an -time algorithm to test whether an -vertex directed partial -tree is upward planar. This result improves upon the previously best known algorithm, which…
Backdoors to Tractable Valued CSP
Robert Ganian, M. S. Ramanujan, Stefan Szeider
We extend the notion of a strong backdoor from the CSP setting to the Valued CSP setting (VCSP, for short). This provides a means for augmenting a class of tractable VCSP instances…
Combining Treewidth and Backdoors for CSP
Robert Ganian, M. S. Ramanujan, Stefan Szeider
We show that CSP is fixed-parameter tractable when parameterized by the treewidth of a backdoor into any tractable CSP problem over a finite constraint language. This result combin…