David ILCINKAS
David Ilcinkas Chargé de Recherches (CNRS)

Équipe LaBRI : Combinatoire et Algorithmique
Équipe projet commune INRIA-LaBRI : CEPAGE
Fonction administrative : Correspondant BMI et SCD. Resp. Adj de l'Equipe CombiAlgo
Page personnelle : http://www.labri.fr/~ilcinkas/
Courrier électronique : david.ilcinkasarobaselabri.fr
Bureau : 361
Tél : +33 (0)5 40 00 69 12


Recherche

Ma thèse de doctorat a porté sur la complexité en espace du problème de l'exploration de graphes : un agent mobile se déplace de sommet en sommet le long des arêtes d'un graphe dont il ignore la structure, et a pour tâche de visiter au moins une fois tous les sommets du graphe. Ce problème est motivé par ses applications en logique, complexité, et bien sûr en robotique. Mes recherches se sont depuis étendues au calcul par agents mobiles et au domaine de l'algorithmique répartie en général. Je porte souvent dans mes travaux un intérêt particulier aux liens entre la quantité de mémoire disponible d'une part et l'existence et l'efficacité de solutions au problème étudié d'autre part.


Principales publications:

[ACM TALG 2008]
Alors qu'aucun agent mobile de mémoire constante n'est capable d'explorer tous les graphes, mêmes planaires de degré maximum~3, cet article montre qu'il existe un agent mobile de mémoire constante et un algorithme coloriant les sommets de tout graphe en seulement trois couleurs tels que cet agent explore avec succès tout graphe ainsi colorié.

[JCSS 2009]
Cet article introduit la notion de conseil comme mesure de la difficulté de problèmes du calcul distribué. Le concept de conseil permet d'étudier quantitativement l'impact des connaissances données aux n{\oe}uds du réseau sur les performances que ces n{\oe}uds peuvent atteindre pour résoudre un problème donné. Dans cet article, nous appliquons cet outil aux tâches apparemment similaires du réveil et de la diffusion (en utilisant un nombre linéaire de messages) pour montrer une différence quantitative de difficulté entre celles-ci.

[DISC 2008]
Un trou noir est un n{\oe}ud d'un réseau qui détruit tout agent y entrant sans laisser de trace détectable. L'emplacement du trou noir doit être déterminé par une une équipe d'agents mobiles identiques déployée à partir d'un emplacement sain. Nous prouvons dans cet article que, pour ce problème, le modèle des cailloux idéaux (un caillou ne peut être placé que sur les n{\oe}uds, et pas plus d'un caillou ne peut être placé sur un n{\oe}ud donné) est aussi puissant que le modèle des tableaux blancs (zone de mémoire présente sur chaque n{\oe}ud accessible en lecture/écriture).

Extrait de publications













Page mise à jour le 13/08/2010 à 10:56