Skip to main content

Research Repository

Advanced Search

Computing maximum matchings in temporal graphs

Mertzios, G.B.; Molter, H.; Niedermeier, R.; Zamaraev, V.; Zschoche, P.


H. Molter

R. Niedermeier

V. Zamaraev

P. 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 our problem, Maximum Temporal Matching, we are looking for the largest possible number of time-labeled edges (simply time-edges) (e, t) such that no vertex is matched more than once within any time window of ∆ consecutive time slots, where ∆ ∈ N is given. We prove strong computational hardness results for Maximum Temporal Matching, even for elementary cases, as well as fixed-parameter algorithms with respect to natural parameters and polynomial-time approximation algorithms.


Mertzios, G., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (in press). Computing maximum matchings in temporal graphs. Journal of Computer and System Sciences,

Journal Article Type Article
Acceptance Date Apr 21, 2023
Online Publication Date May 4, 2023
Deposit Date May 10, 2023
Publicly Available Date May 5, 2024
Journal Journal of Computer and System Sciences
Print ISSN 0022-0000
Publisher Elsevier
Peer Reviewed Peer Reviewed


This file is under embargo until May 5, 2024 due to copyright restrictions.

You might also like

Downloadable Citations