Matching and Edge Cover in Temporal Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913785973833728 |
|---|---|
| author | Cioni, Lapo Dondi, Riccardo Marino, Andrea Schoeters, Jason Silva, Ana |
| author_facet | Cioni, Lapo Dondi, Riccardo Marino, Andrea Schoeters, Jason Silva, Ana |
| contents | Temporal graphs are a special class of graphs for which a temporal component is added to edges, that is, each edge possesses a set of times at which it is available and can be traversed. Many classical problems on graphs can be translated to temporal graphs, and the results may differ. In this paper, we define the Temporal Edge Cover and Temporal Matching problems and show that they are NP-complete even when fixing the lifetime or when the underlying graph is a tree. We then describe two FPT algorithms, with parameters lifetime and treewidth, that solve the two problems. We also find lower bounds for the approximation of the two problems and give two approximation algorithms which match these bounds. Finally, we discuss the differences between the problems in the temporal and the static framework. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06762 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Matching and Edge Cover in Temporal Graphs Cioni, Lapo Dondi, Riccardo Marino, Andrea Schoeters, Jason Silva, Ana Data Structures and Algorithms Computational Complexity Temporal graphs are a special class of graphs for which a temporal component is added to edges, that is, each edge possesses a set of times at which it is available and can be traversed. Many classical problems on graphs can be translated to temporal graphs, and the results may differ. In this paper, we define the Temporal Edge Cover and Temporal Matching problems and show that they are NP-complete even when fixing the lifetime or when the underlying graph is a tree. We then describe two FPT algorithms, with parameters lifetime and treewidth, that solve the two problems. We also find lower bounds for the approximation of the two problems and give two approximation algorithms which match these bounds. Finally, we discuss the differences between the problems in the temporal and the static framework. |
| title | Matching and Edge Cover in Temporal Graphs |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2504.06762 |