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

icon

3

pages

icon

Documents

Lire un extrait
Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
icon

3

pages

icon

Ebook

Lire un extrait
Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

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˜ ?


Voir icon arrow

Publié par

Nombre de lectures

78

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
Voir icon more
Alternate Text