Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Computing maximum matchings in temporal graphs.

Mertzios, G.B. and Molter, H. and Niedermeier, R. and Zamaraev, V. and Zschoche, P. (2020) 'Computing maximum matchings in temporal graphs.', in 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Dagstuhl, Germany: Dagstuhl Publishing, 27:1-27:14. Leibniz International Proceedings in Informatics (LIPIcs). (154).

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.

Item Type:Book chapter
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
(559Kb)
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
(576Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.4230/LIPIcs.STACS.2020.27
Publisher statement:© George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche; licensed under Creative Commons License CC-BY.
Date accepted:19 December 2019
Date deposited:16 January 2020
Date of first online publication:04 March 2020
Date first made open access:12 June 2020

Save or Share this output

Export:
Export
Look up in GoogleScholar