43 citations · 187 across the 40 of their papers we have counts for
3 papers · 1 filter
The Complexity of Growing a Graph
George B. Mertzios, Othon Michail, George Skretas +2
We study a new algorithmic process of graph growth which starts from a single initial vertex and operates in discrete time-steps, called \emph{slots}. In every slot, the graph grow…
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…
The Complexity of Transitively Orienting Temporal Graphs
George B. Mertzios, Hendrik Molter, Malte Renken +2
In a temporal network with discrete time-labels on its edges, entities and information can only ``flow'' along sequences of edges whose time-labels are non-decreasing (resp. increa…