Vol 6 No 1 (2011)
Articles

Analysis and Comparison of Three Algorithms for the Vertex Cover Problem on Large Graphs with Low Memory Capacities

Eric Angel
IBISC, universite d'Evry
Romain Campigotto
IBISC, universite d'Evry
Christian Laforest
LIMOS, universite Blaise Pascal
Published May 30, 2011
Keywords
  • large graphs,
  • vertex cover,
  • mean analysis of algorithms
How to Cite
Angel, E., Campigotto, R., & Laforest, C. (2011). Analysis and Comparison of Three Algorithms for the Vertex Cover Problem on Large Graphs with Low Memory Capacities. Algorithmic Operations Research, 6(1), Pages 56 - 67. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/15266

Abstract

In this paper, we consider the classical NP-complete VERTEX COVER problem in large graphs. We assume that the size and the access to the input graph impose the following constraints: (1) the input graph must not be modified (integrity of the input instance), (2) the computer running the algorithm has a memory of limited size (compared to the graph) and (3) the result must be sent to an output memory once a new piece of solution is calculated. Despite the severe constraints of the model, we propose three algorithms that satisfy them. We derive exact formulas giving the expected size of the solution they return. This allows us to compare them, in an analytic way. Then, we consider their complexities. We give exact formulas expressing the expected number of requests they perform on the input graph. Again, we compare them analytically. For both comparisons, we show that none of them is better than the two others. The formulas we give can help users to estimate the best balance between quality of the solution and performance.