24 citations · 124 across the 75 of their papers we have counts for
9 papers · 1 filter
Matrix Editing Meets Fair Clustering: Parameterized Algorithms and Complexity
Robert Ganian, Hung P. Hoang, Simon Wietheger
We study the computational problem of computing a fair means clustering of discrete vectors, which admits an equivalent formulation as editing a colored matrix into one with few di…
A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
Ajaykrishnan E S, Robert Ganian, Daniel Lokshtanov +1
A graph is a circle graph if it is an intersection graph of chords of a unit circle. We give an algorithm that takes as input an vertex circle graph , runs in time at mo…
Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy
Robert Ganian, Marlene Gründel, Simon Wietheger
Pearl's Causal Hierarchy (PCH) is a central framework for reasoning about probabilistic, interventional, and counterfactual statements, yet the satisfiability problem for PCH formu…
Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms
Thomas Depian, Simon D. Fink, Robert Ganian +1
In spite of the extensive study of stack and queue layouts, many fundamental questions remain open concerning the complexity-theoretic frontiers for computing stack and queue layou…
The Peculiarities of Extending Queue Layouts
Thomas Depian, Simon D. Fink, Robert Ganian +1
We consider the problem of computing -page queue layouts, which are linear arrangements of vertices accompanied with an assignment of the edges to pages from one to th…
The Computational Complexity of Positive Non-Clashing Teaching in Graphs
Robert Ganian, Liana Khazaliya, Fionn Mc Inerney +1
We study the classical and parameterized complexity of computing the positive non-clashing teaching dimension of a set of concepts, that is, the smallest number of examples per con…