8 papers · 1 filter
Maximizing Reachability via Shifting of Temporal Paths
Argyrios Deligkas, Michelle Döring, Eduard Eiben +2
We examine the problem of maximizing the reachability of a given source in temporal graphs that are given as the union of k temporal paths, i.e., every given path is a sequence of…
Coordinated Motion Planning is FPT on Discretized Simple Polygons
Argyrios Deligkas, Eduard Eiben, Robert Ganian +1
In the coordinated motion planning problem, we are given a graph together with the starting and destination vertices of robots. At each time step, any subset of robots may move…
Minimizing Reachability Times on Temporal Graphs via Shifting Labels
Argyrios Deligkas, Eduard Eiben, George Skretas
We study how we can accelerate the spreading of information in temporal graphs via shifting operations; a problem that captures real-world applications varying from information flo…
Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
Argyrios Deligkas, Michelle Döring, Eduard Eiben +3
We study the parameterized complexity of maximum temporal connected components (tccs) in temporal graphs, i.e., graphs that deterministically change over time. In a tcc, any pair o…
Highly Connected Steiner Subgraph -- Parameterized Algorithms and Applications to Hitting Set Problems
Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan
Given a simple connected undirected graph G = (V, E), a set X \subseteq V(G), and integers k and p, STEINER SUBGRAPH EXTENSION problem asks if there exists a set S \supseteq X with…
Determinantal Sieving
Eduard Eiben, Tomohiro Koana, Magnus Wahlström
We introduce determinantal sieving, a new, remarkably powerful tool in the toolbox of algebraic FPT algorithms. Given a polynomial on a set of variables $X=\{x_1,\ldots,x_n\…