Affordable Access

Temporal Matching on Geometric Graph Data

Authors
  • Picavet, Timothe
  • Nguyen, Ngoc-Trung
  • Bui-Xuan, Binh-Minh
Publication Date
May 10, 2021
Source
HAL-INRIA
Keywords
Language
English
License
Unknown
External links

Abstract

Temporal graphs are the modeling of pairwise and historical interaction in recordings of a dataset. A temporal matching formalizes the planning of pair working sessions of a required duration. We depict algorithms finding temporal matchings maximizing the total workload, by an exact algorithm and an approximation. The exact algorithm is a dynamic programming solving the general case in O*((γ + 1) n) time, where n is the number of vertices, γ represents the desired duration of each pair working session, and O* only focuses on exponential factors. When the input data is embedded in an Euclidean space, called geometric data, our approximation is based on a new notion of temporal velocity. We revise a known notion of static density [van Leeuwen, 2009] and result in a polynomial time approximation scheme for temporal geometric graphs of bounded density. We confront our implementations to known opensource implementation.

Report this publication

Statistics

Seen <100 times