CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

A Heuristic Approach for the Vertex Cover Problem

by Omar Kettani, Faycal Ramdani, Benaissa Tadili
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 82 - Number 4
Year of Publication: 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 },
issue_date = { November 2013 },
volume = { 82 },
number = { 4 },
month = { November },
year = { 2013 },
issn = { 0975-8887 },
pages = { 9-11 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume82/number4/14102-2126/ },
doi = { 10.5120/14102-2126 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:56:52.414203+05:30
%A Omar Kettani
%A Faycal Ramdani
%A Benaissa Tadili
%T A Heuristic Approach for the Vertex Cover Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 82
%N 4
%P 9-11
%D 2013
%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
  1. 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.
  2. 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.
  3. 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).
  4. Chleb M. and Chleb J. , "Crown reductions for the Minimum Weighted Vertex Cover problem" Electronic Colloquium on Computational Complexity, Report No. 101 (2004).
  5. Friedrich T. He J. , "Analyses of Simple Hybrid Algorithms for the Vertex Cover Problem" Evolutionary Computation. MIT Press 2009 .
  6. Clarkson K. , "A modification to the greedy algorithm for the vertex cover problem" IPL, vol 16:23-25,(1983).
  7. 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.
  8. Kuratowski K. , "Sur le problème des courbes gauches en topologie," Fund. Math. ,1930.
  9. Bondy J. A. and Murty U. S. R. , "Graph Theory with Applications," Elsevier Science Publishing Co. , Inc, 1976.
  10. Grötzsch H. , "Ein Dreifarbensatz für dreikreisfreie Netz auf der Kugel," Z. Martin-Luther-Univ. , 1958.
  11. Herschel A. S. , Sir Wm. , "Hamilton's Icosian Game," Quart. J. Pure Applied Math.
  12. Ramsey F. P. , On a problem of formal logic, Proc. London Math. Soc. , 1930.
  13. Folkman J. , "Regular line-symmetric graphs," J. Combinatorial Theory, 1967.
  14. Coxeter H. S. M. and Tutte W. T. , "The Chords of the Non-Ruled Quadratic in PG(3,3)," Canad. J. Math. , 1958.
  15. Thomassen C. , Hypohamiltonian and hypotraceable graphs, Discrete Math. , 1974.
Index Terms

Computer Science
Information Sciences

Keywords

Minimum Vertex Cover problem heuristic algorithm

Powered by PhDFocusTM