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

Authors

  • Eric Angel IBISC, universite d'Evry
  • Romain Campigotto IBISC, universite d'Evry
  • Christian Laforest LIMOS, universite Blaise Pascal

Keywords:

large graphs, vertex cover, mean analysis of algorithms

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.

Downloads

Published

2011-05-30

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

Issue

Vol. 6 No. 1 (2011)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.