14 citations · 49 across the 47 of their papers we have counts for
12 papers · 1 filter
The Parameterized Complexity of Coordinated Motion Planning
Eduard Eiben, Robert Ganian, Iyad Kanj
In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which robots occupy distinct starting gridpoints and need to reach distinct destination gridpoi…
A Structural Complexity Analysis of Synchronous Dynamical Systems
Eduard Eiben, Robert Ganian, Thekla Hamm +1
Synchronous dynamic systems are well-established models that have been used to capture a range of phenomena in networks, including opinion diffusion, spread of disease and product…
Finding a Cluster in Incomplete Data
Eduard Eiben, Robert Ganian, Iyad Kanj +2
We study two variants of the fundamental problem of finding a cluster in incomplete data. In the problems under consideration, we are given a multiset of incomplete -dimensional…
The Computational Complexity of Concise Hypersphere Classification
Eduard Eiben, Robert Ganian, Iyad Kanj +2
Hypersphere classification is a classical and foundational method that can provide easy-to-process explanations for the classification of real-valued and binary data. However, obta…
The Complexity of Envy-Free Graph Cutting
Argyrios Deligkas, Eduard Eiben, Robert Ganian +2
We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspon…
Some coordination problems are harder than others
Argyrios Deligkas, Eduard Eiben, Gregory Gutin +2
In order to coordinate players in a game must first identify a target pattern of behaviour. In this paper we investigate the difficulty of identifying prominent outcomes in two kin…