Nina Klobas — accepted AI-conference papers

2022

The Complexity of Temporal Vertex Cover in Small-Degree Graphs

Thekla Hamm, Nina Klobas, George B. Mertzios, Paul G. Spirakis

AAAI 2022technical

Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems Temporal Vertex Cover (or TVC) and Sliding-Window Temporal Vertex Cover (or Delta-TVC for time-windows of a fixed-length Delta) have been established as natural extensions of the classic Vertex…

Cited by 22 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 ↗