6 papers
Parameterized Hardness of Mixed 2-Sided Orthant Depth
Michelle Döring, Georg Tennigkeit
We consider the maximum-depth problem for mixed 2-sided orthants in R^d: each region imposes one lower bound and one upper bound on distinct coordinates, and the task is to find a…
Reconfiguration of Temporal Networks under Reachability Constraints
Othon Michail, George Skretas, Georg Tennigkeit +1
Temporal networks model dynamic systems in which edges represent interactions and labels specify when these interactions occur. Examples include transportation networks, time-sensi…
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…
Parameterized Complexity of Temporal Connected Components
Argyrios Deligkas, Michelle Döring, Eduard Eiben +3
We study the parameterized complexity of maximum temporal connected components (tccs) in temporal graphs, that is, graphs whose edges are available only at specific points in time.…
Temporal Graph Reconfiguration for Always-Connected Graphs
Paul Sievers, George Skretas, Georg Tennigkeit
Network redesign problems ask for modifications to the edges of a given graph to satisfy certain properties. In temporal graphs, where edges are only active at certain times, we ar…
How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs
Argyrios Deligkas, Michelle Döring, Eduard Eiben +3
Logistics and transportation networks require a large amount of resources to realize necessary connections between locations and minimizing these resources is a vital aspect of pla…