45 citations · 170 across the 28 of their papers we have counts for
38 papers
Parameterized Enumeration of Minimal Defensive Alliances
Henning Fernau, Kevin Mann, Arne Meier +1
In this paper, we consider the complexity of enumerating inclusion minimal defensive alliances. We present a polynomial-delay algorithm on graphs with maximum degree 5. We compleme…
Recurrent Graph Neural Networks and Arithmetic Circuits
Timon Barlag, Vivian Holzapfel, Laura Strieker +2
We characterise the computational power of recurrent graph neural networks (GNNs) in terms of arithmetic circuits over the real numbers. Our networks are not restricted to aggregat…
Graph Neural Networks and Arithmetic Circuits
Timon Barlag, Vivian Holzapfel, Laura Strieker +2
We characterize the computational power of neural networks that follow the graph neural network (GNN) architecture, not restricted to aggregate-combine GNNs or other particular typ…
Parameterized Complexity of Weighted Team Definability
Juha Kontinen, Yasir Mahmood, Arne Meier +1
In this article, we study the complexity of weighted team definability for logics with team semantics. This problem is a natural analogue of one of the most studied problems in par…
Enumeration Classes Defined by Circuits
Nadia Creignou, Arnaud Durand, Heribert Vollmer
We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration probl…
Enumerating Teams in First-Order Team Logics
Anselm Haak, Arne Meier, Fabian Müller +1
We start the study of the enumeration complexity of different satisfiability problems in first-order team logics. Since many of our problems go beyond DelP, we use a framework for…