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.