Algorithmique et Programmation Projet Algorithme“Measure and Conquer”pour Maximum Independent Set

Description

Algorithmique et Programmation Projet : Algorithme“Measure and Conquer”pour Maximum-Independent-Set Ecole normale superieure Departement d'informatique 2011-2012 1 Contexte On s'interesse au probleme des gardiens de musee. Un musee est schematiquement forme de couloirs, ou des peintures sont accrochees. Les couloirs doivent etre surveilles par des gardiens. Quand un gardien est positionne au croisement de plusieurs couloirs, il surveille tous les couloirs attenants. Les gardiens du musee en question, tout comme la direction, ont a coeur que la surveillance ait effectivement lieu. Pour assurer le coup, la direction a utilise un algorithme glouton pour assigner les gardiens a des croisements. Cependant, il semble aux gardiens qu'ils sont legerement en sur-effectif, et que certains d'entre eux pourraient faire la sieste ou sortir pendant que les autres assurent la surveillance. C'est une nouvelle illustration du fait qu'un travailleur efficace est un faineant malin. Ils cherchent donc a determiner le nombre strictement minimal de gardiens necessaires a la surveillance du musee, afin de profiter davantage de la vie. Formellement, les couloirs du musee sont les aretes d'un graphe, et le probleme consiste a placer des gardiens sur les sommets de ce graphe de telle sorte que chaque arete soit attenante a un gardien (au moins). On cherche a placer le moins de gardien possible.

• clique


• taille


• return max


• maximum independent


• gardien


• i˜ ?

Sujets

• Clique
• Taille
• Gardien

Informations

• Publié par: pefav
• Nombre de lectures: 78

Extrait

Algorithmique et Programmation Projet : Algorithme“Measure and Conquer”pour Maximum-Independent-Set

Ecolenormalesupe´rieure De´partementd’informatique [e-mail] 2011-2012

1 Contexte Ons’inte´resseauprobl`emedesagdrs´eedemuiensu.lUcnomrsoi,tame´hcstseee´sude´ermfontmeueiq o`udespeinturessontaccroch´ees.Lescouloirsdoiventeˆtresurveill´espardesgardiens.Quandungardien estpositionne´aucroisementdeplusieurscouloirs,ilsurveilletouslescouloirsattenants.Lesgardiensdu muse´eenquestion,toutcommeladirection,ontacoeurquelasurveillanceaiteffectivementlieu.Pour assurerlecoup,ladirectionautilise´unalgorithmegloutonpourassignerlesgardiens`adescroisements. Cependant,ilsembleauxgardiensqu’ilssontle´ge`rementensur-effectif,etquecertainsd’entreeux pourraient faire la sieste ou sortir pendant que les autres assurent la surveillance. C’est une nouvelle illustrationdufaitqu’untravailleurefficaceestunfaine´antmalin.Ilscherchentdonca`d´eterminerle nombrestrictementminimaldegardiensne´cessaires`alasurveillancedumuse´e,afindeprofiterdavantage de la vie. Formellement,lescouloirsdumus´eesontlesareˆtesd’ungraphe,etleproble`meconsistea`placerdes gardienssurlessommetsdecegraphedetellesortequechaqueareˆtesoitattenante`aungardien(au moins).Oncherchea`placerlemoinsdegardienpossible.Onneconnaıˆtpasd’algorithmepolynomialpour r´esoudreceprobl`eme(quiestenfaitleMinimum Vertex Covert.lempcoP-eNuaapssga`lmeeets).Leprob

2 Terminologie Dans un graphe arbitraire, uneCliquesouitontreus´elibmesedelmmosqstenuneetsdsue-xa`d-ue.x Tr`esclairement,dansungraphe,latailledelaplusgrandecliquedugrapheestbiend´efinie.Leprobl`eme Maximum-cliquequliecuneruvroatlamixamelliatederaphe.edansungts`enoisc Demˆeme,unIndependent Setest un ensemble de sommets qui ne sontpase´eserileux(ntreneaucu pairen’estrelie´e).C’estdonclecontraired’uneclique,etilyaunecorrespondanceentrelescliquesd’un 2 grapheetlesindependentsetsdugraphecompl´ementaire(o`uE=V−E). Aussi, les algorithmes de cliquesmaximumetdemaximumindependentsetsontessentiellementlameˆmechose,a`conditionde compl´ementerlegraphe. Enfin, unVertex Coveresarˆetesdugrapheu.qItlinu’oehsctteuoetlsemnsedblomestsmeseenut pasdifficiledevoirquelecompl´ementaired’unindependentsetestunvertexcover.Parcons´equent,un Minimum Vertex Coverˆtuepetboerteri’dnuuna`aptrMaximum Independent Setenemt.piceuqor,´rte Ilestamusantdenoterqueleproble`medetrouverunMinimum Edge Coverpllepeusttiredia--`st’e,c ensembled’arˆetesquitouchetouslessommets,estluisolubleentempspolynomial(vialecalculd’un couplage maximal). ´ On note Γ(xcajdstnemmosastel)`saexerangedphdsuanattnodnnno´n.eE-ensembl´eunsousW deV, lesous-graphe induit parWe´edofmrpaehelrgstemetsssomWesdsearˆeettdeEqui relient des sommets deW. Le´egrded’un sommet est son nombre de voisins.

3 Algorithme“Measure and Conquer” L’algorithmequiportelenom“MeasureandConquer”ae´t´ed´ecriten2006parFormin,Grandoni etKratsch[1].C’estunalgorithme“diviserpourre´gner”,maisavecuntasd’astuces.Cesauteursd´e-   0.2888n montrentquel’algorithmes’ex´ecuteentempsO2 dansle pire des cas, ce qui est plus rapide que l’algorithme de Bron-Kerbosch dans le pire des cas (cependant le“measure and conquer”n’est a priori

1