50 citations · 97 across the 11 of their papers we have counts for
5 papers · 1 filter
Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity
Jan Dreier, Robert Ganian, Marlene Gründel +2
The Boolean Satisfiability (SAT) problem is a remarkably expressive computational problem, serving both as a cornerstone of complexity theory and as a unifying language for a wide…
A Uniform Algorithm for Strict NP on Bounded-Treedepth Graphs
Thomas Depian, Robert Ganian, Jakob Greilhuber +2
A classical well-quasi-ordering result guarantees the existence of non-uniform linear-time algorithms for all problems in Strict NP on relational structures of bounded treedepth; h…
Improved Learning with Structure: Fine-Grained Complexity of Minimum Consistent Subset
Robert Ganian, Manolis Vasilakis, Simon Wietheger
Instance selection is a vital technique for mitigating the computational bottlenecks of nearest-neighbor classification in large-scale supervised clustering. A classical theoretica…
Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
Tian Bai, Fedor V. Fomin, Petr A. Golovach +2
Rank aggregation seeks a representative permutation for a collection of rankings and plays a central role in areas such as social choice, information retrieval, and computational b…
Fair Correlation Clustering Meets Graph Parameters
Johannes Blaha, Robert Ganian, Katharina Gillig +2
We study the generalization of Correlation Clustering which incorporates fairness constraints via the notion of fairlets. The corresponding Fair Correlation Clustering problem has…