01 Timed Matching in Bipartite Temporal Graphs Temporal graphs are introduced to model dynamic networks where the set of edges andor nodes can change with time. In this paper, we define 01 timed matching for temporal graphs, and address the problem of finding the maximum 01 timed matching for bipartite temporal graphs. We show that the problem is NPComplete for bipartite temporal graphs even when each edge is associated with exactly one time interval. We also show that the problem is NPComplete for rooted temporal trees even when each edge is associated with at most three time intervals. Finally, we propose an (O(n3)) time algorithm for the problem on a rooted temporal tree with n nodes when each edge is associated with exactly one time interval.

Cover Time in EdgeUniform StochasticallyEvolving Graphs We define a general model of stochasticallyevolving graphs, namely the edgeuniform stochasticallyevolving graphs. In this model, each possible edge of an underlying general static graph evolves independently being either alive or dead at each discrete time step of evolution following a (Markovian) stochastic rule. The stochastic rule is identical for each possible edge and may depend on the past     k xe2x89xa5 0     observations of the edgexe2x80x99s state. We examine two kinds of random walks for a single agent taking place in such a dynamic graph: (i) The Random Walk with a Delay (RWD), where at each step, the agent chooses (uniformly at random) an incident possible edge, i.e., an incident edge in the underlying static graph, and then, it waits till the edge becomes alive to traverse it. (ii) The more natural Random Walk on what is Available (RWA), where the agent only looks at alive incident edges at each time step and traverses one of them uniformly at random. Our study is on bounding the cover time, i.e., the expected time until each node is visited at least once by the agent. For RWD, we provide a first upper bound for the cases     k  0 , 1     by correlating RWD with a simple random walk on a static graph. Moreover, we present a modified electrical network theory capturing the     k  0     case. For RWA, we derive some first bounds for the case     k  0    , by reducing RWA to an RWDequivalent walk with a modified delay. Further, we also provide a framework that is shown to compute the exact value of the cover time for a general family of stochasticallyevolving graphs in exponential time. Finally, we conduct experiments on the cover time of RWA in edgeuniform graphs and compare the experimental findings with our theoretical bounds.