Show simple item record

dc.contributor.authorBentz, Cédric
dc.contributor.authorCosta, Marie-Christine
dc.contributor.authorde Werra, Dominique
dc.contributor.authorPicouleau, Christophe
dc.contributor.authorRies, Bernard
dc.contributor.authorZenklusen, R.
dc.date.accessioned2020-06-25T07:52:10Z
dc.date.available2020-06-25T07:52:10Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20891
dc.description.abstractfrSoit G = (V, E) un graphe simple non orienté et sans boucle. Nous notons |V | = n, |E| = m et ν(G) la cardinalité maximale d’un couplage. Nous définissons un d-bloqueur comme un ensemble d’arêtes B ⊂ E telque ν((V, E \ B)) ≤ ν(G) − d et un d-transversal comme un ensemble d’arêtes T ⊂ E tel que |M ∩ T| ≥ d pour tout couplage maximum M. Un d-bloqueur (resp. d-transversal) est dit minimum lorsque sa cardinalité |B| (resp. |T|) est minimale. Pour d = 1 un d-bloqueur (resp.transversal) est appelé bloqueur (resp. transversal). Ainsi un transversal correspond à un transversal de l’hypergraphe des couplages maximums de G. De cette façon, les problèmes de d-bloqueurs sont proches des problèmes qui consistent à oter un nombre minimum d’arêtes d’un graphe afin que le graphe partiel obtenu respecte une une propriété donnée. Nous montrons certaines propriétés reliant d-bloqueurs et d-transversaux : tout d-bloqueur est un d-transversal ; il existe des d-transversaux qui ne sont pas des d-bloqueurs. Concernant la complexité algorithmique, nous montrons que pour tout d ∈ {1, . . . , ν(G)}, la recherche d’un d-bloqueur (resp.d-transversal) minimum est un problème NP-difficile même lorsque G est biparti. Nous montrons ensuite comment déterminer un d-bloqueur (resp. d-transversal) minimum lorsque G est une grille ou un arbre : pour une grille de dimension m × n la cardinalité d’un d-bloqueur (resp. d-transversal) minimum est obtenue par une formule close dépendant de d, m, n ; elle est obtenue en utilisant la programmation dynamique dans le cas d’un arbre.en
dc.language.isofren
dc.subjectbloqueursen
dc.subjecttransversauxen
dc.subjectcouplages maximauxen
dc.subject.ddc003en
dc.titled-bloqueurs et d-transversauxen
dc.typeCommunication / Conférence
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.conftitle10ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 09)en
dc.relation.confdate2009-02
dc.relation.confcityNancyen
dc.relation.confcountryFranceen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceNationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2020-06-25T07:44:15Z
hal.person.labIds
hal.person.labIds
hal.person.labIds
hal.person.labIds
hal.person.labIds989
hal.person.labIds


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record