Nous nous sommes intéressés à un problème d'optimisation sur des graphes (le Vertex Cover) dans un contexte de traitement bien particulier : celui des grandes instances de données. Nous avons défini pour cela un modèle de traitement basé sur des contraintes liées principalement à la quantité de mémoire limitée, modèle qui reprenait des propriétés issues de plusieurs modèles existants dans la littérature (online, streaming...). Nous avons étudié plusieurs algorithmes adaptés à ce modèle : nous avons analysé, tout d'abord de façon théorique, la qualité de leurs solutions ainsi que leurs complexités (en pire cas et en moyenne). Nous avons ensuite mené une étude expérimentale sur de très gros graphes.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00677774 |
| Date | 06 December 2011 |
| Creators | Campigotto, Romain |
| Publisher | Université d'Evry-Val d'Essonne |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | fra |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0126 seconds