Philipp Zschoche — accepted AI-conference papers

2022

Disentangling the Computational Complexity of Network Untangling

Vincent Froese, Pascal Kunz, Philipp Zschoche

IJCAI 2022poster

We study the recently introduced network untangling problem, a variant of Vertex Cover on temporal graphs---graphs whose edge set changes over discrete time steps. There are two versions of this problem. The goal is to select at most k time intervals for each vertex such that all time-edges are cove…

Cited by 10 Source ↗PDF ↗Scholar ↗

2021

Interference-free Walks in Time: Temporally Disjoint Paths

Nina Klobas, George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Philipp Zschoche

IJCAI 2021poster

We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing time steps. Two paths (or walks) are temporally disjo…

Cited by 32 Source ↗PDF ↗Scholar ↗