Temporal matching

DOI10.1016/J.TCS.2019.03.026MaRDI QIDQ2285132zbMATH OpenOpenAlexFDO

Authors Julien Baste, Binh-Minh Bui-Xuan, Antoine Roux

Publication date 16 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.08615

zbMATH Keywords

graphparameterized algorithmlink streamopen source code

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: A link stream is a sequence of pairs of the form $(t,u,v)$, where $tinmathbbN$ represents a time instant and $ueqv$. 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^{\prime },u,v)|t^{\prime }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.

Recommendations

• Maximum 0-1 timed matching on temporal graphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• 0-1 timed matching in bipartite temporal graphs
• Computing maximal cliques in link streams
• Enumerating maximal cliques in link streams with durations

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 7238962 (Why is no real title available?)
• Algorithmic applications of Baur-Strassen's theorem, shortest cycles, diameter, and matchings
• Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs
• Computing maximal cliques in link streams
• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• Graph colouring and the probabilistic method
• Machine Learning: ECML 2004
• On the advice complexity of online bipartite matching and online stable marriage
• On the power of advice and randomization for online bipartite matching
• Paths, Trees, and Flowers
• Popular Matchings
• The Power of Linear-Time Data Reduction for Maximum Matching
• Traveling salesman problems in temporal graphs
• Two-sided online bipartite matching and vertex cover: beating the greedy algorithm

Cited in

(17)

• On Computing the Diameter of (Weighted) Link Streams
• Multistage graph problems on a global budget
• Computing maximum matchings in temporal graphs.
• On computing the diameter of (weighted) link streams
• Approximating multistage matching problems
• A faster parameterized algorithm for temporal matching
• Approximating multistage matching problems
• Computing maximum matchings in temporal graphs
• Computing maximal cliques in link streams
• Pattern matching in link streams: timed-automata with finite memory
• Cluster editing for multi-layer and temporal graphs
• Pattern matching in link streams: a token-based approach
• scientific article; zbMATH DE number 4185082 (Why is no real title available?)
• 0-1 timed matching in bipartite temporal graphs
• Maximum 0-1 timed matching on temporal graphs
• Temporal matching on geometric graph data
• Enumerating maximal cliques in link streams with durations

Describes a project that uses

Uses Software

• cliques

This page was built for publication: Temporal matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2285132)