Skip to Main content Skip to Navigation
Theses

Algorithmes d'approximation à mémoire limitée pour le traitement de grands graphes : le problème du Vertex Cover

Abstract : We are interested to an optimization problem on graphs (the Vertex Cover) in a very specific context: the huge instances of data. We defined a treatment model based on constraints linked to the limited amount of memory, model for which properties comes from several existing models in the litterature (online, streaming...). We studied several algorithms suitable to this model: we analyzed, first theoretically, the quality of their solutions and their complexities (in worst and average case). We then conducted an experimental study on very large graphs.
Document type :
Theses
Complete list of metadatas

Cited literature [132 references]  Display  Hide  Download

https://tel.archives-ouvertes.fr/tel-00677774
Contributor : Frédéric Davesne <>
Submitted on : Friday, March 9, 2012 - 4:03:35 PM
Last modification on : Tuesday, June 30, 2020 - 11:56:08 AM
Long-term archiving on: : Thursday, June 14, 2012 - 5:44:17 PM

Identifiers

  • HAL Id : tel-00677774, version 1

Collections

Citation

Romain Campigotto. Algorithmes d'approximation à mémoire limitée pour le traitement de grands graphes : le problème du Vertex Cover. Recherche opérationnelle [cs.RO]. Université d'Evry-Val d'Essonne, 2011. Français. ⟨tel-00677774⟩

Share

Metrics

Record views

484

Files downloads

1035