Ioan Todinca

Professeur

Groupe de recherche : Graphes, algorithmes et modèles de calcul (GAMoC)
Directeur de thèse : Vincent Bouchitté.

Comment me contacter

  • Adresse :
    • LIFO, Universite d'Orleans, 
    BP 6759
    45067 Orleans Cedex 2
  • Téléphone : 02 38 41 72 93
  • Fax : 02 38 41 71 37

    • E-mail : Ioan POINT Todinca @ univ-orleans.fr

Thèmes de recherche :

Je m'intéresse aux décompositions arborescentes de graphes, qui sont une technique pour  représenter des graphes quelconques comme des arbres généralisés. A tout graphe on associe alors un paramètre, la largeur arborescente (treewidth), et l'on peut considérer que plus ce paramètre est petit, plus le graphe a une structure proche d'un arbre.
Beaucoup de problèmes NP-difficiles peuvent être résolus en temps "raisonnable" (exponentiel en la largeur arborescente, mais linéaire en le nombre de sommets) pour les graphes de largeur arborescente bornée. Nous avons abordé le problème du calcul et de l'approximation de la largeur arborescente pour certaines classes de graphes. Nous nous sommes également intéressés aux complétions d'intervalles minimales et à la largeur linéaire (pathwidth) des graphes.

Je travaille aussi sur des algorithmes exacts pour la résolution de problès NP-difficiles et aux algorithmes distribués dans les graphes.

Voir aussi la page publications.

Enseignement

Retours...