24 citations · 124 across the 75 of their papers we have counts for
7 papers · 1 filter
A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots
Eduard Eiben, Robert Ganian, Iyad Kanj +1
We study a variant of the Coordinated Motion Planning problem on undirected graphs, referred to herein as the \textsc{Coordinated Sliding-Motion Planning} (CSMP) problem. In this v…
Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy
Argyrios Deligkas, Eduard Eiben, Robert Ganian +2
We study the parameterized complexity of a generalization of the coordinated motion planning problem on graphs, where the goal is to route a specified subset of a given set of …
Solving Integer Linear Programs with a Small Number of Global Variables and Constraints
Pavel Dvořák, Eduard Eiben, Robert Ganian +2
Integer Linear Programming (ILP) has a broad range of applications in various areas of artificial intelligence. Yet in spite of recent advances, we still lack a thorough understand…
On the Complexity of Rainbow Coloring Problems
Eduard Eiben, Robert Ganian, Juho Lauri
An edge-colored graph is said to be rainbow connected if between each pair of vertices there exists a path which uses each color at most once. The rainbow connection number, de…
FO Model Checking of Interval Graphs
Robert Ganian, Petr Hlineny, Daniel Kral +3
We study the computational complexity of the FO model checking problem on interval graphs, i.e., intersection graphs of intervals on the real line. The main positive result is that…
Better algorithms for satisfiability problems for formulas of bounded rank-width
Robert Ganian, Petr Hliněný, Jan Obdržálek
We provide a parameterized polynomial algorithm for the propositional model counting problem #SAT, the runtime of which is single-exponential in the rank-width of a formula. Previo…