Research Article
A Heuristic Approach for the Vertex Cover Problem
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 82 - Issue 4 |
| Published: November 2013 |
| Authors: Omar Kettani, Faycal Ramdani, Benaissa Tadili |
10.5120/14102-2126
|
Omar Kettani, Faycal Ramdani, Benaissa Tadili . A Heuristic Approach for the Vertex Cover Problem. International Journal of Computer Applications. 82, 4 (November 2013), 9-11. DOI=10.5120/14102-2126
@article{ 10.5120/14102-2126,
author = { Omar Kettani,Faycal Ramdani,Benaissa Tadili },
title = { A Heuristic Approach for the Vertex Cover Problem },
journal = { International Journal of Computer Applications },
year = { 2013 },
volume = { 82 },
number = { 4 },
pages = { 9-11 },
doi = { 10.5120/14102-2126 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2013
%A Omar Kettani
%A Faycal Ramdani
%A Benaissa Tadili
%T A Heuristic Approach for the Vertex Cover Problem%T
%J International Journal of Computer Applications
%V 82
%N 4
%P 9-11
%R 10.5120/14102-2126
%I Foundation of Computer Science (FCS), NY, USA
Abstract
A vertex cover is a subset of the vertex set of a given graph G such that every edge in G has at least one endpoint in this set. The Minimum Vertex Cover problem consists to find the minimum sized vertex cover in a graph. This problem which belongs to the class of NP-hard graph theoretical problems, has many practical applications in various fields. In this article, we propose a novel heuristic algorithm for solving this problem. The test results obtained on some graph examples available in the literature confirm the effectiveness of the proposed method.
References
- Karp R. M. , "Reducibility Among Combinatorial Problems" . In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103.
- Cheetham J. , Dehne F. , Rau-Chaplin A. , Stege U. , Taillon ,P. "Solving large FPT problems on coarse grained parallel machines" Journal of Computer and System Sciences 67 (4) (2003) 691–706.
- Gomes, F. C. , Meneses, C. N. , Pardalos, P. M. , Viana, G. V. R "Experimental analysis of approximation algorithms for the vertex cover and set covering problems" Computers and Operations Research 33(12), 3520–3534 (2006).
- Chleb M. and Chleb J. , "Crown reductions for the Minimum Weighted Vertex Cover problem" Electronic Colloquium on Computational Complexity, Report No. 101 (2004).
- Friedrich T. He J. , "Analyses of Simple Hybrid Algorithms for the Vertex Cover Problem" Evolutionary Computation. MIT Press 2009 .
- Clarkson K. , "A modification to the greedy algorithm for the vertex cover problem" IPL, vol 16:23-25,(1983).
- Alom B. M. , Das S. and Abdur Rouf M. "Performance Evaluation of Vertex Cover and Set Cover Problem using Optimal Algorithm" . DUET Journal Vol. 1, Issue 2, June 2011.
- Kuratowski K. , "Sur le problème des courbes gauches en topologie," Fund. Math. ,1930.
- Bondy J. A. and Murty U. S. R. , "Graph Theory with Applications," Elsevier Science Publishing Co. , Inc, 1976.
- Grötzsch H. , "Ein Dreifarbensatz für dreikreisfreie Netz auf der Kugel," Z. Martin-Luther-Univ. , 1958.
- Herschel A. S. , Sir Wm. , "Hamilton's Icosian Game," Quart. J. Pure Applied Math.
- Ramsey F. P. , On a problem of formal logic, Proc. London Math. Soc. , 1930.
- Folkman J. , "Regular line-symmetric graphs," J. Combinatorial Theory, 1967.
- Coxeter H. S. M. and Tutte W. T. , "The Chords of the Non-Ruled Quadratic in PG(3,3)," Canad. J. Math. , 1958.
- Thomassen C. , Hypohamiltonian and hypotraceable graphs, Discrete Math. , 1974.
Index Terms
Keywords