Lip6, Université Pierre et Marie Curie
Titre: Le polyèdre des sous-graphes
bipartis induits, conception de circuits VLSI et
génomique.
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.