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.
