Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

Algorithmique et Programmation Projet : Algorithme“Measure and Conquer”pour Maximum-Independent-Set
Ecolenormalesupe´rieure De´partementdinformatique td-algo@di.ens.fr 2011-2012
1 Contexte Onsinte´resseauprobl`emedesagdrs´eedemuiensu.lUcnomrsoi,tame´hcstseee´sude´ermfontmeueiq o`udespeinturessontaccroch´ees.Lescouloirsdoiventeˆtresurveill´espardesgardiens.Quandungardien estpositionne´aucroisementdeplusieurscouloirs,ilsurveilletouslescouloirsattenants.Lesgardiensdu muse´eenquestion,toutcommeladirection,ontacoeurquelasurveillanceaiteectivementlieu.Pour assurerlecoup,ladirectionautilise´unalgorithmegloutonpourassignerlesgardiens`adescroisements. Cependant,ilsembleauxgardiensquilssontle´ge`rementensur-eectif,etquecertainsdentreeux pourraient faire la sieste ou sortir pendant que les autres assurent la surveillance. C’est une nouvelle illustrationdufaitquuntravailleurecaceestunfaine´antmalin.Ilscherchentdonca`d´eterminerle nombrestrictementminimaldegardiensne´cessaires`alasurveillancedumuse´e,andeproterdavantage de la vie. Formellement,lescouloirsdumus´eesontlesareˆtesdungraphe,etleproble`meconsistea`placerdes gardienssurlessommetsdecegraphedetellesortequechaqueareˆtesoitattenante`aungardien(au moins).Oncherchea`placerlemoinsdegardienpossible.Onneconnaıˆtpasdalgorithmepolynomialpour 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´enie.Leprobl`eme Maximum-cliquequliecuneruvroatlamixamelliatederaphe.edansungts`enoisc Demˆeme,unIndependent Setest un ensemble de sommets qui ne sontpase´eserileux(ntreneaucu pairenestrelie´e).Cestdonclecontraireduneclique,etilyaunecorrespondanceentrelescliquesdun 2 grapheetlesindependentsetsdugraphecompl´ementaire(o`uE=VE). Aussi, les algorithmes de cliquesmaximumetdemaximumindependentsetsontessentiellementlameˆmechose,a`conditionde compl´ementerlegraphe. Enfin, unVertex Coveresarˆetesdugrapheu.qItlinuoehsctteuoetlsemnsedblomestsmeseenut pasdiciledevoirquelecompl´ementairedunindependentsetestunvertexcover.Parcons´equent,un Minimum Vertex Coverˆtuepetboerteridnuuna`aptrMaximum Independent Setenemt.piceuqor,´rte Ilestamusantdenoterqueleproble`medetrouverunMinimum Edge Coverpllepeusttiredia--`ste,c ensembledarˆetesquitouchetouslessommets,estluisolubleentempspolynomial(vialecalculdun 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” LalgorithmequiportelenomMeasureandConquerae´t´ed´ecriten2006parFormin,Grandoni etKratsch[1].Cestunalgorithmediviserpourre´gner,maisavecuntasdastuces.Cesauteursd´e-  0.2888n montrentquelalgorithmesex´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