David ILCINKAS
David Ilcinkas Chargé de Recherches (CNRS)

Équipe LaBRI : Combinatoire et Algorithmique
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

Pour des informations plus à jour, se référer à ma page personnelle (hhtps://www.labri.fr/perso/ilcinkas/).

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


David Ilcinkas. Oblivious Robots on Graphs: Exploration. Paola Flocchini; Giuseppe Prencipe; Nicola Santoro. Distributed Computing by Mobile Entities, 11340, Springer, pp.218-233, 2019, Lecture Notes in Computer Science, 978-3-030-11071-0. ⟨10.1007/978-3-030-11072-7_9⟩. ⟨hal-02127691⟩

Evangelos Bampas, Jurek Czyzowicz, Leszek Gąsieniec, David Ilcinkas, Ralf Klasing, et al.. Linear Search by a Pair of Distinct-Speed Robots. Algorithmica, Springer Verlag, 2019, 81 (1), pp.317-342. ⟨10.1007/s00453-018-0447-0⟩. ⟨hal-01872346⟩

Evangelos Bampas, Lélia Blin, Jurek Czyzowicz, David Ilcinkas, Arnaud Labourel, et al.. On asynchronous rendezvous in general graphs. Theoretical Computer Science, Elsevier, 2019, 753, pp.80-90. ⟨https://www.sciencedirect.com/science/article/pii/S0304397518304614?via%3Dihub⟩. ⟨10.1016/j.tcs.2018.06.045⟩. ⟨hal-01900843⟩

Stéphane Devismes, David Ilcinkas, Colette Johnen. Silent self-stabilizing scheme for spanning-tree-like constructions. ICDCN 2019, Jan 2019, Bangalore, India. pp.158-167, ⟨10.1145/3288599.3288607⟩. ⟨hal-02127131⟩

Evangelos Bampas, Jurek Czyzowicz, David Ilcinkas, Ralf Klasing. Beachcombing on strips and islands. Theoretical Computer Science, Elsevier, In press, ⟨10.1016/j.tcs.2019.04.001⟩. ⟨hal-02127575⟩


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