Skip to Main content Skip to Navigation
Conference papers

Temporal matching in link stream: kernel and approximation

Julien Baste 1, 2 Binh-Minh Bui-Xuan 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download
Contributor : Binh-Minh Bui-Xuan Connect in order to contact the contributor
Submitted on : Thursday, March 21, 2019 - 4:15:39 PM
Last modification on : Tuesday, January 4, 2022 - 3:51:02 AM
Long-term archiving on: : Saturday, June 22, 2019 - 3:59:09 PM


Files produced by the author(s)


  • HAL Id : hal-02075831, version 1


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



Les métriques sont temporairement indisponibles