24 citations · 124 across the 75 of their papers we have counts for
10 papers · 1 filter
A Parameterized-Complexity Framework for Finding Local Optima
Robert Ganian, Hung P. Hoang, Christian Komusiewicz +1
Local search is a fundamental optimization technique that is both widely used in practice and deeply studied in theory, yet its computational complexity remains poorly understood.…
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…
Pathways to Tractability for Geometric Thickness
Thomas Depian, Simon Dominik Fink, Alexander Firbas +2
We study the classical problem of computing geometric thickness, i.e., finding a straight-line drawing of an input graph and a partition of its edges into as few parts as possible…
A Structural Complexity Analysis of Hierarchical Task Network Planning
Cornelius Brand, Robert Ganian, Fionn Mc Inerney +1
We perform a refined complexity-theoretic analysis of three classical problems in the context of Hierarchical Task Network Planning: the verification of a provided plan, whether an…
Approximate Evaluation of Quantitative Second Order Queries
Jan Dreier, Robert Ganian, Thekla Hamm
Courcelle's theorem and its adaptations to cliquewidth have shaped the field of exact parameterized algorithms and are widely considered the archetype of algorithmic meta-theorems.…
A Parameterized Theory of PAC Learning
Cornelius Brand, Robert Ganian, Kirill Simonov
Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory, and efficient PAC learnability is often seen as a natural counterpart to the clas…