Computing Maximum Matchings in Temporal Graphs

George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev & Philipp Zschoche
Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching, taking into account the dynamic nature of temporal graphs. In...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.