Temporal Matching - Sorbonne Université
Article Dans Une Revue Theoretical Computer Science Année : 2020

Temporal Matching

Résumé

A link stream is a sequence of pairs of the form $(t,\{u,v\})$, where $t\in\mathbb N$ represents a time instant and $u\neq v$. Given an integer $\gamma$, the $\gamma$-edge between vertices $u$ and $v$, starting at time $t$, is the set of temporally consecutive edges defined by $\{(t',\{u,v\}) | t' \in [t,t+\gamma-1]\}$. We introduce the notion of temporal matching of a link stream to be an independent $\gamma$-edge set belonging to the link stream. We show that the problem of computing a temporal matching of maximum size is NP-hard as soon as $\gamma>1$. We depict a kernelization algorithm parameterized by the solution size for the problem. As a byproduct we also give a $2$-approximation algorithm. Both our $2$-approximation and kernelization algorithms are implemented and confronted to link streams collected from real world graph data. We observe that finding temporal matchings is a sensitive question when mining our data from such a perspective as: managing peer-working when any pair of peers $X$ and $Y$ are to collaborate over a period of one month, at an average rate of at least two email exchanges every week. We furthermore design a link stream generating process by mimicking the behaviour of a random moving group of particles under natural simulation, and confront our algorithms to these generated instances of link streams. All the implementations are open source.
Fichier principal
Vignette du fichier
S0304397519301914.pdf (1.14 Mo) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02075865 , version 1 (21-07-2022)

Licence

Identifiants

Citer

Julien Baste, Binh-Minh Bui-Xuan, Antoine Roux. Temporal Matching. Theoretical Computer Science, 2020, ⟨10.1016/j.tcs.2019.03.026⟩. ⟨hal-02075865⟩
330 Consultations
22 Téléchargements

Altmetric

Partager

More