0000000000846378
AUTHOR
Benoit Darties
showing 6 related works from this author
ADM : A Density And Priority Levels Aware Protocol For Broadcasting In Vehicular Ad-Hoc Networks
2014
The broadcasting communication mode is widely used in Vehicular Ad~hoc Networks (VANETs). It is used for sending emergency messages, road-traffic information or to help routing protocols to determine routes. This communication mode is known to be hard to achieve efficiently since it depends on the network density. Indeed, broadcasting methods may cause network congestion if they are not well designed. This paper introduces a novel Autonomic Dissemination Method (ADM) which delivers messages in accordance with given message classes and network density levels. The proposed approach is based on two steps: an offline optimization process and an online adaptation to the network characteristics. …
Scheduling coupled-tasks with incompatibility constraint: a bin-packing related problem
2014
International audience; We tackle the makespan minimization problem of coupled- tasks in presence of compatibility constraint. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. We show the relationship with bin packing problems for some configurations, and study several problems in framework of complexity and approximation for which the topology of the compatibility graph is specific (star, chain, bipartite, . . .).
Arbres couvrants presque disjoints
2015
International audience; Dans un réseau, la recherche de plusieurs arbres couvrants avec des propriétés intéressantes a amené à l'introduc-tion de plusieurs notions : les arbres couvrants arête-disjoints, les arbres indépendants enracinés en un sommet et les arbres complètement indépendants. Afin de généraliser ces notions, nous introduisons la notion d'arbres couvrants (i, j)-disjoints, où i et j sont respectivement le nombre maximum de noeuds internes et d'arêtes communs aux arbres couvrants. Nous montrons que déterminer s'il existe deux arbres couvrants (i, j)-disjoints dans un graphe G est un problème NP-complet pour i et j quelconques, et nous déterminons les valeurs minimales de i et j…
Scheduling stretched coupled-tasks with compatibilities constraints : model, complexity and approximation results for some class of graphs
2014
We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, {\it i.e.}coupled-tasks having the same sub-tasks execution time and idle time duration. We study severals problems in frame works of classic complexity and approximation for which the compatibility graph $G_c$ is bipartite (star, chain, $\ldots$) In such context, we design some efficient polynomial-time approximation algorithms according to difference parameters of the scheduling problem. When $G_c$ is a $k$-stage bipartite graph, we propose, among other, a $\frac{7}{6}$-approximation algorithm when $k=1$, and a $\frac{13}{9}$-approximation…
Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph
2012
International audience; This paper presents a generalization of the coupled-task sche-duling problem introduced by Shapiro \cite{Shapiro}, where considered tasks are subject to incompatibility constraints depicted by an undirected graph. The motivation of this problem comes from data acquisition and processing in a mono-processor torpedo used for underwater exploration. As we add the compatibility graph, we focus on complexity of the problem, and more precisely on the boundary between $\mathcal{P}$ and $\mathcal{NP}$-completeness when some other input parameters are restricted (e.g. the ratio between the durations of the two sub-tasks composing a task): we adapt the global visualization of …
Gestion autonome des communications dans les réseaux ad hoc de véhicules : cas de la diffusion
2013
National audience