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.

Computing maximum matchings in temporal graphs Thumbnail


Authors

H. Molter

R. Niedermeier

V. Zamaraev

P. Zschoche



Contributors

Christophe Paul
Editor

Markus Blaser
Editor

Abstract

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 Δ ∈ ℕ is given. The requirement that a vertex cannot be matched twice in any Δ-window models some necessary "recovery" period that needs to pass for an entity (vertex) after being paired up for some activity with another entity. We prove strong computational hardness results for Maximum Temporal Matching, even for elementary cases. To cope with this computational hardness, we mainly focus on fixed-parameter algorithms with respect to natural parameters, as well as on polynomial-time approximation algorithms.

Citation

Mertzios, G., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2020). Computing maximum matchings in temporal graphs. In C. Paul, & M. Blaser (Eds.), 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) (27:1-27:14). https://doi.org/10.4230/lipics.stacs.2020.27

Conference Name 37th International Symposium on Theoretical Aspects of Computer Science (STACS)
Conference Location Montpellier, France
Acceptance Date Dec 19, 2019
Online Publication Date Mar 4, 2020
Publication Date Mar 1, 2020
Deposit Date Dec 23, 2019
Publicly Available Date Jun 12, 2020
Pages 27:1-27:14
Series Title Leibniz International Proceedings in Informatics (LIPIcs)
Series Number 154
Series ISSN 1868-8969
Book Title 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
DOI https://doi.org/10.4230/lipics.stacs.2020.27
Public URL https://durham-repository.worktribe.com/output/1141315
Related Public URLs https://arxiv.org/pdf/1905.05304.pdf

Files






You might also like



Downloadable Citations