Ioan Todinca

Professeur

Curriculum Vitae
Groupe de recherche : Graphes et algorithmes
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. Plus récemment, nous nous sommes intéressés aux complétions d'intervalles minimales et à la largeur linéaire (pathwidth) des graphes.

Voir aussi la page publications.

Enseignement

Retours...