Back to Search
Start Over
Computing maximum matchings in temporal graphs.
- Source :
-
Journal of Computer & System Sciences . Nov2023, Vol. 137, p1-19. 19p. - Publication Year :
- 2023
-
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 Δ ∈ 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *APPROXIMATION algorithms
*BIPARTITE graphs
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 137
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 164156406
- Full Text :
- https://doi.org/10.1016/j.jcss.2023.04.005