**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**32731

##### Optimization of Unweighted Minimum Vertex Cover

**Authors:**
S. Balaji,
V. Swaminathan,
K. Kannan

**Abstract:**

**Keywords:**
vertex cover,
vertex support,
approximation algorithms,
NP - complete problem.

**Digital Object Identifier (DOI):**
doi.org/10.5281/zenodo.1079664

**References:**

[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.