Algorithmes de graphes cours MPRI 2007-2008Algorithmes de graphescours MPRI 2007-2008Pierre Fraigniaud et Michel HabibPierre.Fraigniaud@liafa.jussieu.fr, habib@liafa.jussieu.frChateau des rentiers, septembre 2007Algorithmes de graphes cours MPRI 2007-2008Algorithmes de graphescours MPRI 2007-2008Pierre Fraigniaud et Michel HabibPierre.Fraigniaud@liafa.jussieu.fr, habib@liafa.jussieu.frChateau des rentiers, septembre 2007Algorithmes de graphes cours MPRI 2007-2008PlanIntroductionQuels algorithmes?Structuration et d´ecompositionPr´esentation du coursProblems and ExercisesGraph RepresentationsAlgorithmes de graphes cours MPRI 2007-2008IntroductionIntroductionQuels algorithmes?Structuration et d´ecompositionPr´esentation du coursProblems and ExercisesGraph RepresentationsAlgorithmes de graphes cours MPRI 2007-2008IntroductionQuestion initialePourquoi ´etudier l’algorithmique de graphes?Algorithmes de graphes cours MPRI 2007-2008IntroductionQuestion initialePourquoi ´etudier l’algorithmique de graphes?Les th´eor`emes de FaginCaract´erisant P et NP en termes de graphes et de logique.Algorithmes de graphes cours MPRI 2007-2008IntroductionQuestion initialePourquoi ´etudier l’algorithmique de graphes?Les th´eor`emes de FaginCaract´erisant P et NP en termes de graphes et de logique.NPThe class of all graph-theoretic properties expressible in existentialsecond-order logic is precisely NP.Algorithmes de graphes cours MPRI ...