**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**30750

##### Approximating Maximum Weighted Independent Set Using Vertex Support

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

**Abstract:**

**Keywords:**
heuristic,
vertex support,
weighted independent set,
vertex cover,
NP - hard problem

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

**References:**

[1] L. Babel: A fast algorithm for the maximum weight clique problem, Computing, (1994), Vol. 52, pp. 31-38.

[2] S.Balaji, V. Swaminathan & K. Kannan: An Effective Algorithm for Minimum Weighted Vertex Cover problem, to be appear in International Journal of Computational and Mathematical Sciences, Vol.4 (1) (2010), pp. 34-38.

[3] B. Bollobas: Random graphs (2nd Ed.). Cambridge, UK: Cambridge University press (2001)

[4] I. Bomze, M. Budinich, M. Pellilo & Rossic: Annealed Replication: A new heuristic for the maximum clique problem, Discrete Applied Mathematics, (2002), Vol. 121, pp. 27-49.

[5] I. Bomze, M. Pellilo & V. Stix: Approximating the maximum weight clique using replicator dynamics, IEEE Transactions Neural Network, (2000), vol. 11.

[6] P. Crescenzi, C. Fiorini & R. Silvestri: A note on the approximation of the max. clique problem, Information Processing Letters, (1991), vol. 40, No.1, pp. 1-5.

[7] S. De Vries & R. Vohra: Combinatorial auctions: a survey, INFORMS Journal on Computing (2003), vol. 15, pp. 284-309.

[8] DIMACS clique benchmarks, Benchmark instances made available by electronic transfer at dimacs.rutgers.edu, Rutgers Univ., Piscataway. NJ. (1993).

[9] T. Etzion & P. R. J. stergrd: Greedy and heuristic algorithms for codes and colorings, IEEE Transactions on Information Theory, (1998), vol. 44, pp. 382-388.

[10] U. Feige, S. Goldwasser, L. Lovasz, S. Safra & M. Szegedy: Approximating clique is almost NP-complete, Proceedings of the 32nd IEEE Annual symposium on Foundations of computer science, San Juan, Paerto Rico, (1991), pp. 2 -12.

[11] E. J. Gardiner, P. J. Artymink & P. Willett: Clique detection algorithms for matching three-dimensional structures, Journal of Molecular Graphics and Modeling, (1998), vol. 15, pp. 245-253.

[12] M. R. Garey, D. S. Johnson: Computers and Intractability: A Guide to the theory NP - completeness, San Francisco: Freeman (1979).

[13] A. Mehrotra & M. A. Trick: A Column generation approach for graph coloring, INFORMS Journal on Computing (1996), vol. 8, pp. 344-354.

[14] P R J Ostergard: A New Algorithm for the Maximum Weight Clique problem, Nordic Journal of Computing, (2001), vol. 8, pp 424-436.

[15] P. Pardolos & J. Xue: The maximum clique problem, Journal of Global optimization, (1994), vol.4, pp. 301-328.

[16] P. A. Pevzner & S. H. Sze: Combinatorial approaches to finding subtle signals in DNA sequences, Proceedings of Eighth International Conference on intelligent systems for Molecular Biology, AAAI Press, (2000), pp.269-278.

[17] W. Pullan: Approximating the maximum vertex/edge weighted clique using local search, Jounal of Heuristics, (2008), vol. 14, pp. 117-134.

[18] W. Pullan: Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers, Discrete Optimization, (2009), vol. 6, pp. 214-219.

[19] M. Weight & A. K. Hartmann: Minimal vertex covers on finiteconnectivity random graphs - A hard-sphere lattice-gas picture, Phys. Rev. E, 63, 056127.