Temporal matching in link stream: kernel and approximation - Sorbonne Université
Communication Dans Un Congrès Année : 2018

Temporal matching in link stream: kernel and approximation

Résumé

A link stream is a sequence of pairs of the form (t, {u, v}), where t ∈ N represents a time instant and u = v. Given an integer γ, the γ-edge between vertices u and v, starting at time t, is the set of temporally consecutive edges defined as {(t , {u, v}) | t ∈ t, t + γ − 1}. We introduce the notion of temporal matching of a link stream to be a set of pairwise non overlapping γ-edges belonging to the link stream. Unexpectedly, the problem of computing a temporal matching of maximum size turns out to be N P-hard. We provide a kernelization algorithm parameterized by the solution size for the problem. As a byproduct we also depict a 2-approximation algorithm.
Fichier principal
Vignette du fichier
temporalMatchingCTW18.pdf (326.8 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02075831 , version 1 (21-03-2019)

Identifiants

  • HAL Id : hal-02075831 , version 1

Citer

Julien Baste, Binh-Minh Bui-Xuan. Temporal matching in link stream: kernel and approximation. CTW 2018 - 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Jun 2018, Paris, France. ⟨hal-02075831⟩
201 Consultations
79 Téléchargements

Partager

More