L. and E. Est-donc-le-meilleur-en-terme-de-complexité-en-nombre-de-requêtes, Il est suivi par l'algorithme LR, qui doit sadeuxì eme place en grande partie au fait que les algorithmes LL, SLL et ASLL peuvent effectuer (contrairementàcontrairementà lui) plus de m requêtes. Il est suivi de près par l'algorithme ASLL, qui effectue moins souvent plus de m requêtes que LL et SLL et qui est bon sur certains graphes

. Dans, algorithme S-Pitt est globalement moyen sur l'ensemble des graphes. Il n'atteint et ne dépasse jamais m requêtes. Les algorithmes LL et SLL effectuent assez souvent plus de m requêtes, Mais contrairementàcontrairementà SLL, LL peut parfoisêtreparfoisêtre bon sur les graphes aléatoires en loi de puissance

L. , E. Pitt, L. Sll-m, and A. , 1.4, les temps d'exécution sont exprimés en user + system time. Pour obtenir une estimation des temps réelsréelsécoulés, il faut multiplier en moyenne par 2,5 les temps de création fournis par les tableaux 4, Comme nous l'avons précisé dans la section 4 SLL et ASLL), il faut multiplier en moyenne par 3
URL : https://hal.archives-ouvertes.fr/hal-00479005

L. Algorithmes and S. , ASLL se distinguent des autres algorithmes puisqu'ils utilisent une tête de lecture supplémentaire pour pouvoir récupérer les degrés des voisins. Leurs temps d'exécution sont donc difficilement comparables aux autres. Nous allons donc nous intéressés principalement aux algorithmes LR

. De-façon-générale, objet d'un traitement sur le processeur de la machine (par exemple, une comparaison entre deux labels pour LL ou un test d'appartenancè a la mémoire pour ED) En revanche, la taille des solutions joue essentiellement sur le system time, puisque l'on se contente d'´ ecrire sur le disque externe (après avoir effectuer un traitement suitè a une requête) On peut d'ailleurs observer sur l'instance hypercube-30 (voir le tableau 4.14 page 118) que l'algorithme ED, quí ecrit deux fois plus de sommets que l'algorithme LR, a un system time deux fois plus grand. Cependant, ces deux paramètres ne suffisent pasàpasà interpréter les temps d'exécution. D'autres aspects techniques, liés notamment aux principes de fonctionnement des systèmes d'exploitation (voir par exemple [25]), entrent en jeu. Par exemple, l'accès au disque externe n'est pas direct : pour effectuer ses entrées/sorties, la machine de traitement utilise des tampons. Ainsi, même si l'on récupère uniquement un voisin dans le fichier .list, le système en charge en réalité un certain nombre (cette quantité est liée entre autresàautresà la taille des secteurs sur le disque) Par conséquent, le nombre d'accès physiques au disque externe est, la plupart du temps, inférieur au nombre de requêtes effectuées 5 . De ce fait, on ne peut pas identifier demanì ere certaine une relation entre les temps d'exécution des algorithmes, le nombre de requêtes qu'ils effectuent et le nombre de sommets qu'ilsécriventilsécrivent. En effet LL, qui effectue quatre fois moins de requêtes que LR, met quatre fois moins de tempsàtempsà s'exécuter

P. Mattiåstrandmattiåstrand, V. Floréen, J. Polishchuk, J. Rybicki, J. Suomela et al., A Local 2-approximation Algorithm for the Vertex Cover Problem, DISC '09 : Proceedings of the 23rd International Conference on Distributed Computing, pp.191-205

J. Abello, A. L. Buchsbaum, and J. R. Westbrook, A Functional Approach to External Graph Algorithms, Algorithmica, vol.32, issue.3, pp.437-458, 2002.
DOI : 10.1007/s00453-001-0088-5

N. Faisal, M. A. Abu-khzam, P. Langston, C. T. Shanbhag, and . Symons, Scalable Parallel Algorithms for FPT Problems, Algorithmica, vol.45, issue.3, pp.269-284, 2006.

A. Aggarwal and J. S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, vol.31, issue.9, pp.1116-1127, 1988.
DOI : 10.1145/48529.48535

URL : https://hal.archives-ouvertes.fr/inria-00075827

G. Aggarwal, M. Datar, M. Sridhar-rajagopalan, and . Ruhl, On the Streaming Model Augmented with a Sorting Primitive, 45th Annual IEEE Symposium on Foundations of Computer Science, pp.540-549, 2004.
DOI : 10.1109/FOCS.2004.48

K. Jin-ahn and S. Guha, Linear Programming in the Semi-Streaming Model with Application to the Maximum Matching Problem, 1104.

D. Ajwani and . Design, Implementation and Experimental Study of External Memory BFS Algorithms, 2005.

S. Albers, Online algorithms: a survey, Mathematical Programming, vol.97, issue.1, pp.3-26, 2003.
DOI : 10.1007/s10107-003-0436-0

Y. Noga-alon, M. Matias, and . Szegedy, The Space Complexity of Approximating the Frequency Moments, Journal of Computer and System Sciences, vol.58, issue.1, pp.137-147, 1996.
DOI : 10.1006/jcss.1997.1545

N. Alon and J. H. Spencer, The Probabilistic Method, 1992.

E. Angel, R. Campigotto, and C. Laforest, Algorithms for the Vertex Cover Problem on Large Graphs, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00653634

E. Angel, R. Campigotto, and C. Laforest, Comparaison d'algorithmes pour le probì eme du Vertex Cover sur de grands graphes, ROADEF, 2010.

E. Angel, R. Campigotto, and C. Laforest, Analysis and Comparison of Three Algorithms for the Vertex Cover Problem on Large Graphs with Low Memory Capacities, Algorithmic Operations Research, vol.6, issue.1, pp.56-67, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00653634

L. Arge, U. Meyer, L. Toma, and N. Zeh, On External-Memory Planar Depth First Search, Journal of Graph Algorithms and Applications, vol.7, issue.2, pp.105-129, 2003.
DOI : 10.7155/jgaa.00063

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.118.2231

L. Arge and N. Zeh, I/O-efficient strong connectivity and depth-first search for directed planar graphs, 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pp.261-270, 2003.
DOI : 10.1109/SFCS.2003.1238200

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM, vol.45, issue.3, pp.501-555, 1998.
DOI : 10.1145/278298.278306

S. Arora and S. Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM, vol.45, issue.1, pp.70-122, 1998.
DOI : 10.1145/273865.273901

E. Asgeirsson and C. Stein, Vertex Cover Approximations on Random Graphs, LNCS, vol.4525, pp.285-296, 2007.
DOI : 10.1007/978-3-540-72845-0_22

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.6764

D. Avis and T. Imamura, A list heuristic for vertex cover, Operations Research Letters, vol.35, issue.2, pp.201-204, 2006.
DOI : 10.1016/j.orl.2006.03.014

B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '02, pp.1-16, 2002.
DOI : 10.1145/543613.543615

R. Bar-yehuda and S. Even, A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem, Annals of Discrete Mathematics, vol.25, pp.27-46, 1985.
DOI : 10.1016/S0304-0208(08)73101-3

R. Bar-yehuda, D. Hermelin, and D. Rawitz, Minimum Vertex Cover in Rectangle Graphs, ESA '10 : Proceedings of the 18th Annual European Conference on Algorithms, Part I, pp.255-266, 2010.

J. Beauquier and B. Bérard, Systèmes d'exploitation : concepts et algorithmes, 2001.

B. Behsaz, P. Hatami, and E. S. Mahmoodian, On Minimum Vertex Cover of Generalized Petersen Graphs, Australasian Journal of Combinatorics, vol.40, pp.253-264, 2008.

E. Birmelé, F. Delbot, and C. Laforest, Mean analysis of an online algorithm for the vertex cover problem, Information Processing Letters, vol.109, issue.9, pp.436-439, 2009.
DOI : 10.1016/j.ipl.2008.12.021

A. Borodin and R. El-yaniv, Online Computation and Competitive Analysis, 1998.

B. Bre?ar, F. Kardo?, J. Katreni?, and G. Semani?in, Minimum <mml:math altimg="si1.gif" display="inline" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd"><mml:mi>k</mml:mi></mml:math>-path vertex cover, Discrete Applied Mathematics, vol.159, issue.12, pp.1189-1195, 2011.
DOI : 10.1016/j.dam.2011.04.008

J. Cardinal, M. Karpinski, R. Schmied, and C. Viehmann, Approximating vertex cover in dense hypergraphs, Journal of Discrete Algorithms, vol.13, 1012.
DOI : 10.1016/j.jda.2012.01.003

URL : http://arxiv.org/abs/1012.2573

J. Cardinal, M. Labbé, S. Langerman, E. Levy, and H. Mélot, A Tight Analysis of the Maximal Matching Heuristic, COCOON '05 : Proceedings of the 11th Annual International Computing and Combinatorics Conference, pp.701-709, 2005.
DOI : 10.1007/11533719_71

URL : https://hal.archives-ouvertes.fr/hal-01255575

Y. Caro, New Results on the Independence Number, 1979.

D. A. Cartwright, M. A. Cueto, and E. A. Tobis, The Maximum Independent Sets of de Bruijn Graphs of Diameter 3, Electronic Journal of Combinatorics, 2010.

F. H. Chang, H. Fu, F. K. Hwang, and B. C. Lin, The minimum number of <mml:math altimg="si3.gif" display="inline" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd"><mml:mi>e</mml:mi></mml:math>-vertex-covers among hypergraphs with <mml:math altimg="si4.gif" display="inline" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd"><mml:mi>e</mml:mi></mml:math> edges of given ranks, Discrete Applied Mathematics, vol.157, issue.1, pp.164-169, 2009.
DOI : 10.1016/j.dam.2008.05.006

Y. Chang and Y. Lin, A Fast and Memory Efficient Dynamic IP Lookup Algorithm Based on B-Tree, 2009 International Conference on Advanced Information Networking and Applications, 2009.
DOI : 10.1109/AINA.2009.63

M. Charikar, O. Liadan, R. Callaghan, and . Panigrahy, Better streaming algorithms for clustering problems, Proceedings of the thirty-fifth ACM symposium on Theory of computing , STOC '03, pp.30-39, 2003.
DOI : 10.1145/780542.780548

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.8875

E. Y. Chen, Geometric Streaming Algorithms with a Sorting Primitive, Proceedings of the 18th International Symposium on Algorithms and Computation, volume LNCS 4835, pp.512-524, 2007.

J. Chen, I. A. Kanj, and W. Jia, Vertex Cover: Further Observations and Further Improvements, Journal of Algorithms, vol.41, issue.2, pp.280-301, 2001.
DOI : 10.1006/jagm.2001.1186

URL : http://anyserver.cityu.edu.hk/weijia/publication/vertex_cover.pdf

J. Chen, I. A. Kanj, and G. Xia, Improved Parameterized Upper Bounds for Vertex Cover, MFCS '06 : Proceedings of the 31st International Symposium of Mathematical Foundations of Computer Science, volume LNCS 4162, pp.238-249, 2006.
DOI : 10.1007/11821069_21

A. Stephen and . Cook, The Complexity of Theorem-Proving Procedures, STOC '71 : Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, pp.151-158, 1971.

M. Geoffrey, R. E. Cooper, and . Hausman, The Cell : a Molecular Approach, 2009.

H. Thomas, C. E. Cormen, R. L. Leiserson, C. Rivest, and . Stein, Introduction to Algorithms, 2009.

C. Courcoubetis, M. Y. Vardi, P. Wolper, and M. Yannakakis, Memory Efficient Algorithms for the Verification of Temporal Properties, Formal Methods in System Design, pp.275-288, 1992.

N. Govert-de-bruijn, A Combinatorial Problem, Koninklijke Nederlandse Akademie v. Wetenschappen, vol.49, pp.758-764, 1946.

F. Delbot, Audeì a de l'´ evaluation en pire cas : comparaison etévaluationetévaluation en moyenne de processus d'optimisation pour leprobì eme du vertex cover et des arbres de connexion de groupes dynamiques, 2009.

F. Delbot and C. Laforest, A better list heuristic for vertex cover, Information Processing Letters, vol.107, issue.3-4, pp.125-127, 2008.
DOI : 10.1016/j.ipl.2008.02.004

URL : https://hal.archives-ouvertes.fr/hal-00341369

F. Delbot and C. Laforest, Analytical and experimental comparison of six algorithms for the vertex cover problem, Journal of Experimental Algorithmics, vol.15, 2011.
DOI : 10.1145/1671970.1865971

M. Demange, V. Th, and . Paschos, On-line vertex-covering, Theoretical Computer Science, vol.332, issue.1-3, pp.83-108, 2005.
DOI : 10.1016/j.tcs.2004.08.015

URL : http://doi.org/10.1016/j.tcs.2004.08.015

R. Dementiev, L. Kettner, and P. Sanders, STXXL : Standard Template Library for XXL Data Sets. Software : Practice and Experience, Librairie disponible sur http, pp.539-637, 2008.
DOI : 10.1002/spe.844

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.113.9084

C. Demetrescu, B. Escoffier, G. Moruz, and A. Ribichini, Adapting Parallel Algorithms to the W-Stream Model, with Applications to Graph Problems, Theoretical Computer Science, vol.411, pp.44-463994, 2010.

C. Demetrescu, I. Finocchi, and A. Ribichini, Trading Off Space for Passes in Graph Streaming Problems, SODA '06 : Proceddings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.714-723, 2006.

I. Dinur and S. Safra, On the hardness of approximating vertex cover, Annals of Mathematics, vol.162, issue.1, pp.439-485, 2005.
DOI : 10.4007/annals.2005.162.439

M. Philip, C. W. Duxbury, and I. Fay, Precise Polynomial Heuristic for an NP-Complete Problem Disponible sur http, 2003.

S. Eggert, L. Kliemann, and A. Srivastav, Bipartite Graph Matchings in the Semi-streaming Model, ESA '09 : Proceedings of the 17th Annual European Symposium on Algorithms, pp.492-503, 2009.
DOI : 10.1007/978-3-642-04128-0_44

B. Escoffier, L. Gourvès, and J. Monnot, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, Journal of Discrete Algorithms, vol.8, issue.1, pp.36-49, 2010.
DOI : 10.1016/j.jda.2009.01.005

URL : https://hal.archives-ouvertes.fr/hal-00178912

J. Feigenbaum, S. Kannan, A. Mcgregor, S. Suri, and J. Zhang, On Graph Problems in a Semi-Streaming Model, Theoretical Computer Science, vol.348, pp.2-3207, 2005.

J. Feigenbaum, S. Kannan, A. Mcgregor, S. Suri, and J. Zhang, Graph Distances in the Data-Stream Model, SIAM Journal on Computing, vol.38, issue.5, pp.1709-1727, 2005.
DOI : 10.1137/070683155

J. Feigenbaum, S. Kannan, and J. Zhang, Computing Diameter in the Streaming and Sliding-Window Models, Algorithmica, vol.41, issue.1, pp.25-41, 2002.
DOI : 10.1007/s00453-004-1105-2

P. Flajolet and G. Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, vol.31, issue.2, pp.182-209, 1985.
DOI : 10.1016/0022-0000(85)90041-8

URL : https://hal.archives-ouvertes.fr/inria-00076244

J. Flum and M. Grohe, Parameterized Complexity Theory, 2006.

P. Fouilhoux and A. R. Mahjoub, Solving VLSI design and DNA sequencing problems using bipartization of graphs, Computational Optimization and Applications, vol.291, issue.2, pp.1-33, 2010.
DOI : 10.1007/s10589-010-9355-1

URL : https://hal.archives-ouvertes.fr/hal-01185262

R. Michael, D. S. Garey, and . Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, 1979.

R. Michael, D. S. Garey, L. Johnson, and . Stockmeyer, Some Simplified NP-Complete Graph Problems, Theoretical Computer Science, vol.1, issue.3, pp.237-267, 1976.

M. Glaymann, Ou le premier n'est pas toujours premier ..., Educational Studies in Mathematics, vol.7, issue.1-2, pp.83-88, 1976.
DOI : 10.1007/BF00144361

O. Goldreich, Property Testing in Massive Graphs, Handbook of Massive Data Sets, pp.123-147, 2002.
DOI : 10.1145/1968.1972

O. Goldreich, S. Goldwasser, and D. Ron, Property testing and its connection to learning and approximation, Journal of the ACM, vol.45, issue.4, pp.653-750, 1998.
DOI : 10.1145/285055.285060

M. Golfarelli and S. Rizzi, Data Warehouse Design : Modern Principles and Methodologies, 2009.

I. Good, Normal Recurring Decimals, Journal of the London Mathematical Society, vol.1, issue.3, pp.167-169, 1946.
DOI : 10.1112/jlms/s1-21.3.167

F. Grandoni, J. Könemann, and A. Panconesi, Distributed Weighted Vertex Cover via Maximal Matchings, ACM Transaction on Algorithms, vol.5, issue.1, 2008.

V. Guruswami and R. O. , Disponible sur http, PCP Course Notes, 2005.

P. Hall, On Representatives of Subsets, Journal of the London Mathematical Society, vol.10, issue.1, pp.26-30, 1935.

V. Bjarni, M. M. Halldórsson, E. Halldórsson, M. Losievskaja, and . Szegedy, Streaming Algorithms for Independent Sets, ICALP '10 : Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming, pp.641-652, 2010.

A. K. Hartmann and M. Weigt, Statistical mechanics of the vertex-cover problem, Journal of Physics A: Mathematical and General, vol.36, issue.43, 2003.
DOI : 10.1088/0305-4470/36/43/028

M. Rauch-heizinger, P. Raghavan, and S. Rajagopalan, Computing on Data Streams, Digital System Search Center, 1998.

C. John and . Venter, The Sequence of the Human Genome, Science, vol.291, pp.1304-1351, 2001.

G. Karakostas, A Better Approximation Ratio for the Vertex Cover Problem, ACM Transactions on Algorithms (TALG), vol.5, issue.4, 2009.

R. M. Karp, Reducibility among Combinatorial Problems, Complexity of Computer Computations, pp.85-103, 1972.
DOI : 10.1007/978-3-540-68279-0_8

K. Dénes, GràfokGràfokés m` atrixok. Matematikaí es Fizikai Lapok, pp.116-119, 1931.

S. Khot and O. Regev, Vertex cover might be hard to approximate to within <mml:math altimg="si1.gif" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd"><mml:mn>2</mml:mn><mml:mo>???</mml:mo><mml:mi>??</mml:mi></mml:math>, Journal of Computer and System Sciences, vol.74, issue.3, pp.335-349, 2008.
DOI : 10.1016/j.jcss.2007.06.019

C. Koufogiannakis and N. E. Young, Distributed and parallel algorithms for weighted vertex cover and other covering problems, Proceedings of the 28th ACM symposium on Principles of distributed computing, PODC '09, pp.171-179, 2009.
DOI : 10.1145/1582716.1582746

E. Kushilevitz and N. Nisan, Communication Complexity, 1997.

G. Lancia, V. Bafna, S. Istrail, R. Lippert, and R. Schwartz, SNPs Problems, Complexity, and Algorithms, pp.182-193, 2001.
DOI : 10.1007/3-540-44676-1_15

H. Lee, H. Kim, and J. Jang, A New Approximated VC Scheme to Prevent D-DoS Attack against Networks of ASes, International Joint Conference on Information and Communication, 2004.

L. Levin, . Universal-'nye-perebornye, and . Zadachi, English translation, Problemy Peredachi Informatsii, vol.9, issue.3, pp.265-266, 1973.

N. Lichiardopol, Independence number of de Bruijn graphs, Discrete Mathematics, vol.306, issue.12, pp.1145-1160, 2006.
DOI : 10.1016/j.disc.2005.10.032

R. Lippert, R. Schwartz, G. Lancia, and S. Istrail, Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem, Briefings in Bioinformatics, vol.3, issue.1, pp.23-31, 2002.
DOI : 10.1093/bib/3.1.23

U. Meyer, On Trade-Offs in External-Memory Diameter-Approximation, SWAT '08 : Proceedings of the 11th Scandinavian Workshop on Algorithm Theory, pp.426-436, 2008.
DOI : 10.1007/978-3-540-69903-3_38

U. Meyer, Efficient Algorithms, chapter Via Detours to I/O-Efficient Shortest Paths, pp.219-232, 2009.
DOI : 10.1007/978-3-642-03456-5_15

M. Molloy and B. Reed, A Critical Point for Random Graphs With a Given Degree Sequence. Random Structures and Algorithms, pp.161-179, 1995.

B. Monien and E. Speckenmeyer, Ramsey numbers and an approximation algorithm for the vertex cover problem, Acta Informatica, vol.8, issue.1, pp.115-123, 1985.
DOI : 10.1007/BF00290149

H. Moser, Exact Algorithms for Generalizations of Vertex Cover, 2005.

R. Motwani and P. Raghavan, Randomized Algorithms, 1995.

S. and M. Muthukrishnan, Data Streams : Algorithms and Applications Disponible sur http, 2003.
DOI : 10.1561/0400000002

URL : http://ce.sharif.edu/courses/90-91/1/ce797-1/resources/root/Data_Streams_-_Algorithms_and_Applications.pdf

S. , M. Muthukrishnan, and A. Mcgregor, Data Streams Algorithms Lecture Notes from Data Streams course at Barbados, 2009.

R. Niedermeier, Invitation to Fixed-Parameter Algorithms, 2006.
DOI : 10.1093/acprof:oso/9780198566076.001.0001

C. O. Thomas and . Connell, Fundamental Problems in Computing, chapter A Survey of Graph Algorithms under Extended Streaming Models of Computation, pp.455-476, 2009.

H. Christos, Papadimitriou and Mihalis Yannakakis. Optimization, Approximation and Complexity Classes, Journal of Computer and System Sciences, vol.43, issue.3, pp.425-440, 1991.

M. Parnas and D. Ron, Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms, Theoretical Computer Science, vol.381, issue.1-3, pp.183-196, 2007.
DOI : 10.1016/j.tcs.2007.04.040

V. Th and . Paschos, Complexité et approximation polynomiale, Hermès Science, 2004.

S. Pérennes and I. S. Valls, Sur la Conjecture des Jeux Uniques, 2008.

S. Pirzada and A. Dharwadker, Applications of graph theory, PAMM, vol.92, issue.1, pp.19-38, 2007.
DOI : 10.1002/pamm.200700981

L. Pitt, A Simple Probabilistic Approximation Algorithm for Vertex Cover, 1985.

I. Razgon, Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3, Journal of Discrete Algorithms, vol.7, issue.2, pp.191-212, 2009.
DOI : 10.1016/j.jda.2008.09.004

S. Richter, M. Helmert, and C. Gretton, A Stochastic Local Search Approach to Vertex Cover, KI '07 : Proceedings of the 30th German Conference on Artificial Intelligence, pp.412-426, 2007.
DOI : 10.1007/978-3-540-74565-5_31

D. Ron, lgorithmic and Analysis Techniques in Property Testing, Foundations and Trends?? in Theoretical Computer Science, vol.5, issue.2, pp.73-205, 2010.
DOI : 10.1561/0400000029

C. Roth-korostensky and E. Zurich, Algorithms for Building Multiple Sequence Alignments and Evolutionary Trees, 2000.

R. Rubinfeld and M. Sudan, Robust Characterizations of Polynomials with Applications to Program Testing, SIAM Journal on Computing, vol.25, issue.2, pp.252-271, 1996.
DOI : 10.1137/S0097539793255151

M. Ruhl, Efficient Algorithms for New Computationnal Models, 2003.

C. Savage, Depth-first search and the vertex cover problem, Information Processing Letters, vol.14, issue.5, pp.233-235, 1982.
DOI : 10.1016/0020-0190(82)90022-9

R. Schwartz, Theory and Algorithms for the Haplotype Assembly Problem, Communications in Information and Systems, vol.10, issue.1, pp.23-38, 2010.
DOI : 10.4310/CIS.2010.v10.n1.a2

K. Smith, Genetic Polymorphism and SNPs Disponible sur http, 2002.

U. Stege, Resolving Conflicts in Problems from Computational Biology, 2000.

V. Turau and B. Hauck, A Self-stabilizing Approximation Algorithm for Vertex Cover in Anonymous Networks, SSS '09 : Proceedings of the 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems, pp.341-353, 2009.
DOI : 10.1007/978-3-642-05118-0_24

V. Vijay and . Vazirani, Approximation Algorithms, 2001.

F. Vigier and M. Latapy, Random Generation of Large Connected Simple Graphs with Prescribed Degree Distribution Programmes disponibles sur http, COCOON '05 : Proceedings of the 11th International Conference on Computing and Combinatorics, 2005.

S. Vishwanathan, On hard instances of approximate vertex cover, ACM Transactions on Algorithms, vol.5, issue.1, 2008.
DOI : 10.1145/1435375.1435382

J. S. Vitter, Algorithms and Data Structures for External Memory, Foundations and Trends?? in Theoretical Computer Science, vol.2, issue.4, 2009.
DOI : 10.1561/0400000014

J. S. Vitter and E. A. Shriver, Algorithms for parallel memory, I: Two-level memories, Algorithmica, vol.30, issue.4, pp.110-147, 1994.
DOI : 10.1007/BF01185207

V. K. Wei, A Lower Bound on the Stability Number of a Simple Graph, 1981.

E. W. Weisstein, Butterfly graph. From MathWorld ? A Wolfram Web Ressource

D. B. West, Introduction to Graph Theory, second edition, 2001.

K. F. Thomas, Y. S. Wong, T. W. Chiu, S. M. Lam, and . Yiu, Memory Efficient Algorithms for Structural Alignment of RNAs with Pseudoknots, IEEE Transactions on Computational Biology and Bioinformatics, vol.6, issue.1, 2007.

A. Yao, Some Complexity Questions Related to Distributive Computing, STOC '79 : Proceedings of the 11th Annual ACM Symposium on Theory of Computing, pp.209-213, 1979.

N. Zeh, Encyclopedia of Algorithms, chapter, 2008.

M. Zelke, Algorithms for Streaming Graphs, Mathematisch- Naturwissenschaftliche Fakultät II, 2009.

M. Zelke, Intractability of min- and max-cut in streaming graphs, Information Processing Letters, vol.111, issue.3, pp.145-150, 2011.
DOI : 10.1016/j.ipl.2010.10.017

R. Daniel, E. Zerbino, and . Birney, Velvet : Algorithms for De Novo Short Read Assembly Using de Bruijn Graphs, Genome Research, vol.18, issue.5, pp.821-829, 2008.

Y. Zhang, Q. Ge, R. Fleisher, T. Jiang, and H. Zhu, Approximating the minimum weight weak vertex cover, Theoretical Computer Science, vol.363, issue.1, pp.99-105, 2006.
DOI : 10.1016/j.tcs.2006.06.009

Z. Zhang, X. Gao, and W. Wu, PTAS for connected vertex cover in unit disk graphs, Theoretical Computer Science, vol.410, issue.52, pp.5398-5402, 2009.
DOI : 10.1016/j.tcs.2009.01.035