3 papers
cs.DS2022
The complexity of computing optimum labelings for temporal connectivity
Nina Klobas, George B. Mertzios, Hendrik Molter +1
A graph is temporally connected if there exists a strict temporal path, i.e. a path whose edges have strictly increasing labels, from every vertex to every other vertex . In…
cs.DS2021
Interference-free Walks in Time: Temporally Disjoint Paths
Nina Klobas, George B. Mertzios, Hendrik Molter +2
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 pa…
math.CO2020
Fast recognition of some parametric graph families
Nina Klobas, Matjaž Krnc
We identify all -cycle regular -graphs and all -cycle regular double generalized Petersen graphs. As a consequence we describe linear recognition algorithm…