Graphes k-partis et conception de circuits VLSI

Graphes k-partis et conception de circuits VLSI

data.idref

Export biblio

Identifiant pérenne de la notice : 247728861

URI de l'entité : http://www.idref.fr/247728861/id

Notice de type Notice de regroupement

Point d'accès autorisé

Graphes k-partis et conception de circuits VLSI

Variante de point d'accès

k-partite graphs and VLSI circuit design

[Notice de regroupement]

Information

Langue d'expression : français

Date de parution : 2004

Notes

Note publique d'information :

Le problème de Via Minimization contraint concerne la dernière étape du processus de conception de circuits VLSI. Pour positionner les réseaux de pistes du circuit sur une carte de façon à ce que 2 segments de réseaux différents ne soient connectés, il est parfois nécessaire de faire des percements dans la carte pour connecter des segments sur des couches différentes. De tels percements sont appelés des vias. Le problème de Via Minimization contraint consiste à déterminer une affectation à des réseaux aux couches qui utilise un nombre minimum de vias. Dans cette thèse, nous étudions ce problème. Nous montrons dans un premier temps que le problème sur k couches se ramène au problème du sous-graphe k-parti induit maximum. Par la suite, nous considérons le problème de Via Minimization dans le cas de 2 couches. Dans ce cas, le problème est équivalent au problème du sous-graphe biparti induit. 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 valides et nous donnons des conditions nécessaires et suffisantes pour que ces contraintes définissent des facettes du polytope. Nous discutons aussi 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 l'algorithme de coupes et branchements basé sur ces résultats pour le problème du sous-graphe biparti induit. Nous utilisons cet algorithme pour résoudre des instances du problème de Via Minimization contraint. Nous étudions aussi le problème général du sous-graphe k-parti induit pour k quelconque. Nous proposons une formulation en nombres entiers pour laquelle nous développons un algorithme de génération de colonnes et branchements. Celui-ci est utilisé pour résoudre des instances du problème de Via Minimization contraint ayant plus de deux couches. 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. Pour le critère dit d'enlèvement minimum de fragments, il a été prouvé que ce problème se ramène au problème du sous-graphe biparti induit de cardinalité maximum. Considérant cette modélisation, nous utilisons notre algorithme de coupes et branchements pour résoudre aussi des instances de ce problème. Nous proposons aussi une modélisation du problème d'assemblage SNP d'haplotypes pour le critère dit du nombre minimum de corrections. Nous montrons que le problème avec ce critère se ramène aussi au problème du sous-graphe biparti induit

Notices d'autorité liées

Informations sur la notice

Identifiant de la notice : 247728861

RCR créateur de la notice : 0499

Date de création : 07-07-2020

RCR dernier modificateur de la notice : 0499

Date de dernière modification : 05-05-2022 à 01 h 37

... Références liées : ...