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

https://hal.sorbonne-universite.fr/hal-02075831
Contributor : Binh-Minh Bui-Xuan <>
Submitted on : Thursday, March 21, 2019 - 4:15:39 PM
Last modification on : Tuesday, March 23, 2021 - 9:28:02 AM
Long-term archiving on: : Saturday, June 22, 2019 - 3:59:09 PM

File

temporalMatchingCTW18.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02075831, version 1

Citation

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⟩

Share

Metrics

Record views

191

Files downloads

64