Partenaires

CNRS
Logo tutelle
Logo tutelle
Logo tutelle

Rechercher

Sur ce site

Sur le Web du CNRS

Accueil du site > Séminaires > Mathématiques des systèmes complexes > Le polyèdre des sous-graphes bipartis induits, conception de circuits VLSI et génomique

Vendredi 8 juin 2007 à 11h00

Le polyèdre des sous-graphes bipartis induits, conception de circuits VLSI et génomique

Pierre Fouilhoux (LIP6, Université Paris 6)

Résumé : Dans cet exposé, nous considérons le problème du sous-graphe biparti induit de poids maximum. Nous étudions le polyèdre associé à ce problème. Nous décrivons plusieurs classes de contraintes valides et nous donnons des conditions nécessaires et suffisantes pour que ces contraintes définissent des facettes du polytope. Nous discutons également d’algorithmes de séparation et nous montrons que certaines de ces classes peuvent être séparées en temps polynomial. Nous développons aussi un algorithme de coupes et branchements basé sur ces résultats pour le problème du sous-graphe biparti induit. Nous proposons ensuite deux applications de ce problème. La première concerne la conception de circuits intégrés de grandes dimensions (VLSI). Plus particulièrement, nous montrons comment le problème de Via Minimization contraint peut se ramener à rechercher un plus grand sous-graphe biparti induit dans un graphe particulier. Enfin, nous nous intéressons au problème d’assemblage SNP d’haplotypes qui constitue une étape du séquençage du génome pour les organismes diploïdes. Sous certains critères, nous montrons que ce problème se ramène également au problème du sous-graphe biparti induit. Enfin, nous appliquons notre algorithme de coupes et branchements pour résoudre des instances issues de ces deux applications.

Dans la même rubrique :