The Minimum Vertex Cover (MVC) problem is a classic
graph optimization NP - complete problem. In this paper a competent
algorithm, called Vertex Support Algorithm (VSA), is designed to
find the smallest vertex cover of a graph. The VSA is tested on a
large number of random graphs and DIMACS benchmark graphs.
Comparative study of this algorithm with the other existing methods
has been carried out. Extensive simulation results show that the VSA
can yield better solutions than other existing algorithms found in the
literature for solving the minimum vertex cover problem.
[1] C. Aggarwal , J. B Orlin and R. P Tai, Optimized cross cover for the
independent set problem, Operations Research, Vol. 45, (1997), 226-234.
[2] P. Berman and T. Fujito, On approximation properties of the independent
set problem for low degree graphs, Theory of Computing Syst., Vol. 32,
(1999), 115 - 132.
[3] B. Bollobas, Random graphs, 2nd Ed., Cambridge, UK: Cambridge
University press (2001).
[4] J. M. Bourjolly , P. Gill , G. Laporte and H. Mercure, An exact quadratic
0-1 algorithm for the stable set problem, American Mathematical Society
Providence, RI. 1996, pp. 53-73.
[5] T. H. C. E. Cormen, R. L. R. Leiserson, and C. Stein, Introduction to
algorithms, 2nd ed., McGraw - Hill, New York (2001).
[6] F. Dehne et. al, Solving large FPT problems on coarse grained parallel
machines, Available: http://www.scs.carleton.ca/fpt/papers/index.htm.
[7] DIMACS clique benchmarks, Benchmark instances made available by
electronic transfer at dimacs.rutgers.edu, Rutgers Univ., Piscataway. NJ.
(1993).
[8] M. R. Fellows, On the complexity of vertex cover problems, Technical
report, Computer science department, University of New Mexico (1988).
[9] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to
the theory NP - completeness, San Francisco: Freeman (1979).
[10] M. R. Garey, D. S. Johnson and L. Stock Meyer, Some simplified NP
- complete graph problems, Theoretical computer science, Vol. 1563,
(1999), 561 - 570.
[11] D. S. Hochbaum Efficient bounds for the stable set, vertex cover and
set packing problems, Discrete Appl. Mathematics, Vol. 6, (1983), 243 -
254.
[12] R. M. Karp, Reducibility among combinatorial problems, Plenum Press,
New York, (1972), pp 85 - 103.
[13] K, Katayama, A. Hamamoto and H. Narihisa, An effective local search
for the maximum clique problem, Information Processing Letters, Vol. 95,
(2005), 503-511.
[14] S. Khuri and T. Back, An evolutionary heuristic for the minimum vertex
cover problem, J. Kunze and H. Stoyan, editors, KI - 94 workshops
(Extended Abstracts), Bonn (1994), pp. 83 - 84..
[15] D. Matula, On the complete subgraph of a random graph, Combinatory
mathematics and its Applications, (1970), pp. 356-369.
[16] B. Monien and E. Speckenmeyer Ramsey numbers and an approximation
algorithm for the vertex cover problems, Acta Informatica, Vol. 22,
(1985), 115 - 123.
[17] W. Pullan, Optimisation of unweighted/weighted maximum independent
sets and minimum vertex covers, Discrete Optimization, Vol. 6, (2009),
214-219.
[18] S.J. Shyu, P.Y. Yin and B.M.T. Lin, An ant colony optimization algorithm
for the minimum weight vertex cover problem, Annals of Operations
Research, Vol. 131, (2004), 283 - 304.
[19] U. Stege, Resolving conflicts from problems in computational Biology,
Ph.D thesis, No.13364, ETH Zurich (2000).
[20] C. Z. Tang, X. Xu et al., An algorithm based on Hopfield network
learning for minimum vertex cover problem, Lecture Notes in computer
science, Vol. 3173, (2004), 430 - 435,.
[21] M. Weight and A. K. Hartmann, The number of guards needed by a
museum - a phase transition in vertex covering of random graphs, Phys
- Rev. Lett., 84, 6118 (2000b).
[22] M. Weight and A. K. Hartmann, Minimal vertex covers on finiteconnectivity
random graphs - A hard-sphere lattice-gas picture, Phys.
Rev. E, 63, 056127.
[23] X. Xu and J. Ma, An efficient simulated annealing algorithm for the
minimum vertex cover problem, Nerocomputing, Vol. 69, Issues 7-9,
(2006), 613 - 616.
[1] C. Aggarwal , J. B Orlin and R. P Tai, Optimized cross cover for the
independent set problem, Operations Research, Vol. 45, (1997), 226-234.
[2] P. Berman and T. Fujito, On approximation properties of the independent
set problem for low degree graphs, Theory of Computing Syst., Vol. 32,
(1999), 115 - 132.
[3] B. Bollobas, Random graphs, 2nd Ed., Cambridge, UK: Cambridge
University press (2001).
[4] J. M. Bourjolly , P. Gill , G. Laporte and H. Mercure, An exact quadratic
0-1 algorithm for the stable set problem, American Mathematical Society
Providence, RI. 1996, pp. 53-73.
[5] T. H. C. E. Cormen, R. L. R. Leiserson, and C. Stein, Introduction to
algorithms, 2nd ed., McGraw - Hill, New York (2001).
[6] F. Dehne et. al, Solving large FPT problems on coarse grained parallel
machines, Available: http://www.scs.carleton.ca/fpt/papers/index.htm.
[7] DIMACS clique benchmarks, Benchmark instances made available by
electronic transfer at dimacs.rutgers.edu, Rutgers Univ., Piscataway. NJ.
(1993).
[8] M. R. Fellows, On the complexity of vertex cover problems, Technical
report, Computer science department, University of New Mexico (1988).
[9] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to
the theory NP - completeness, San Francisco: Freeman (1979).
[10] M. R. Garey, D. S. Johnson and L. Stock Meyer, Some simplified NP
- complete graph problems, Theoretical computer science, Vol. 1563,
(1999), 561 - 570.
[11] D. S. Hochbaum Efficient bounds for the stable set, vertex cover and
set packing problems, Discrete Appl. Mathematics, Vol. 6, (1983), 243 -
254.
[12] R. M. Karp, Reducibility among combinatorial problems, Plenum Press,
New York, (1972), pp 85 - 103.
[13] K, Katayama, A. Hamamoto and H. Narihisa, An effective local search
for the maximum clique problem, Information Processing Letters, Vol. 95,
(2005), 503-511.
[14] S. Khuri and T. Back, An evolutionary heuristic for the minimum vertex
cover problem, J. Kunze and H. Stoyan, editors, KI - 94 workshops
(Extended Abstracts), Bonn (1994), pp. 83 - 84..
[15] D. Matula, On the complete subgraph of a random graph, Combinatory
mathematics and its Applications, (1970), pp. 356-369.
[16] B. Monien and E. Speckenmeyer Ramsey numbers and an approximation
algorithm for the vertex cover problems, Acta Informatica, Vol. 22,
(1985), 115 - 123.
[17] W. Pullan, Optimisation of unweighted/weighted maximum independent
sets and minimum vertex covers, Discrete Optimization, Vol. 6, (2009),
214-219.
[18] S.J. Shyu, P.Y. Yin and B.M.T. Lin, An ant colony optimization algorithm
for the minimum weight vertex cover problem, Annals of Operations
Research, Vol. 131, (2004), 283 - 304.
[19] U. Stege, Resolving conflicts from problems in computational Biology,
Ph.D thesis, No.13364, ETH Zurich (2000).
[20] C. Z. Tang, X. Xu et al., An algorithm based on Hopfield network
learning for minimum vertex cover problem, Lecture Notes in computer
science, Vol. 3173, (2004), 430 - 435,.
[21] M. Weight and A. K. Hartmann, The number of guards needed by a
museum - a phase transition in vertex covering of random graphs, Phys
- Rev. Lett., 84, 6118 (2000b).
[22] M. Weight and A. K. Hartmann, Minimal vertex covers on finiteconnectivity
random graphs - A hard-sphere lattice-gas picture, Phys.
Rev. E, 63, 056127.
[23] X. Xu and J. Ma, An efficient simulated annealing algorithm for the
minimum vertex cover problem, Nerocomputing, Vol. 69, Issues 7-9,
(2006), 613 - 616.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:61710", author = "S. Balaji and V. Swaminathan and K. Kannan", title = "Optimization of Unweighted Minimum Vertex Cover", abstract = "The Minimum Vertex Cover (MVC) problem is a classic
graph optimization NP - complete problem. In this paper a competent
algorithm, called Vertex Support Algorithm (VSA), is designed to
find the smallest vertex cover of a graph. The VSA is tested on a
large number of random graphs and DIMACS benchmark graphs.
Comparative study of this algorithm with the other existing methods
has been carried out. Extensive simulation results show that the VSA
can yield better solutions than other existing algorithms found in the
literature for solving the minimum vertex cover problem.", keywords = "vertex cover, vertex support, approximation algorithms,NP - complete problem.", volume = "4", number = "7", pages = "1001-6", }
