S.V. Listrovoy, A.V. Sidorenko, E.S. Listrovaya
Èlektron. model. 2017, 39(3):17-36
https://doi.org/10.15407/emodel.39.03.017
ABSTRACT
A method of search for the largest maximal independent sets of an undirected connected graph is proposed that allows one to solve the problem of determining the largest maximal independent sets in polynomial time with the number of vertices in the graph not exceeding 120 and the density of edges in the range from 0.067 to 0.9. with a further increase in the number of vertices and a decrease in the density of edges in the graph, the algorithm has an exponential complexity that does not exceed at an average O (20,4n), which tends to the decrease with increasing the edge density in the graph, where n is the number of vertices in the graph.
KEYWORDS
maximal independent set, click, the top cover.
REFERENCES
1. Harary, F. and Ross, I.C. (1957), “A procedure for clique detection using the group matrix”, Sociometry, Vol. 20, pp. 205-215.
https://doi.org/10.2307/2785673
2. Butenko, S. and Wilhelm, W.E. (2006), “Clique-detection models in computational biochemistry and genomics”, European Journal of Operational Research, Vol. 173, pp. 1-17.
https://doi.org/10.1016/j.ejor.2005.05.026
3. Raymond, J.W. and Willett, P. (2002), “Maximum common subgraph isomorphism algorithmsmatching chemical structures”, Journal of Computer-Aided MolecularDesign,Vol. 16, pp. 521-533.
4. Varmuza, K., Penchev, P.N. and Scsibrany, H. (1998), “Maximum common substructures of
organic compounds exhibiting similar infrared spectra”, J. Chem. Inf. Comput. Sci., Vol. 38,
pp. 420-427.
5. Horaud, R. and Skordas, T. (1989), “Stereo correspondence through feature grouping and maximal cliques”, IEEE Trans. Pattern Anal. Mach. Intell., Vol. 11, no. 11.
6. Pelillo, M., Siddiqi, K. and Zucker, S.W. (1999), “Matching hierarchical structures using association graphs”, IEEE Trans. Pattern Anal. Mach. Intell., Vol. 21, no. 11.
7. Shearer, K., Bunke, H. and Venkatesh, S. (2000), Video indexing and similarity retrieval by largest common subgraph detection using decision trees, IDIAP-RR 00-15, Dalle Molle Institute for Perceptual Artificial Intelligence, Martigny, Valais, Switzerland.
8. Shirinivas, S.G., Vetrivel, S. and Elango, N.M. (2010), “Application of graph theory in computer science an overview”, International Journal of Engineering Science and Technology, Vol. 2, no. 9, pp. 4610-4621.
9. Seliverstov, A.V. and Lyubetskiy, V.A. (2006), “Algorithm for the search for conservative segments of nucleotide sequences”, Informatsionnyie protsessy, Vol. 6, no. 1, pp. 33-36.
10. Bahadur, D.K.C., Akutsu, T., Tomita, E. and et al. (2002), “Point matching under non-uniform distortions and protein side chain packing based on efficient maximum clique algorithms”, Genome Inform., Vol. 13, pp. 143-152.
11. Carr, R.D., Lancia, G. and Istrail, S. (2000), Branch-and-cut algorithms for independent set problems: integrality gap and application to protein structure alignment. Technical report, Sandia National Laboratories, Albuquerque, NM (US); Sandia National Laboratories, Livermore, CA (US).
12. Harley, E., Bonner, A. and Goodman, N. (2001), “Uniform integration of genome mapping data using intersection graphs”, Bioinformatics, Vol. 17, pp. 487-494.
13. Samudrala, R. and Moult, J. (1998), “A graph-theoretic algorithm for comparative modeling of protein structure”, J. Mol. Biol., Vol. 279, pp. 287-302.
https://doi.org/10.1006/jmbi.1998.1689
14. Tomita, E., Akutsu, T., Hayashida, M. and et al. (2003), “Algorithms for computing an optimal protein threading with profiles and distance restraints”, Genome Informatics, Vol. 14, pp. 480-481.
15. Bahadur, D.K.C., Tomita, E., Suzuki, J. and et al. (2005), “Protein sidechain packing problem: a maximum edge-weight clique algorithmic approach”, J. Bioinform Comput. Biol., Vol. 3, pp. 103-126.
https://doi.org/10.1142/S0219720005000904
16. Jianer, C., Iyad, K.A. and Ge, X. (2010), “Improved parameterized upper bounds for vertex cover”, Elsevier: Theoretical Computer Science, Vol. 411, pp. 3736-3756.
17. Bron, C. and Kerbosch, J. (1973), “Algorithm 457: Finding all cliques of an undirected graph”, Comm. of ACM, Vol. 16, pp. 575-577.
https://doi.org/10.1145/362342.362367
18. Fomin, F.V., Grandoni, F. and Kratsch, D. (2006), “Measure and conquer: a simple O(20.288n ) independent set algorithm”, Proceedings of the 17th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006.
19. Robson, J.M. (1986), “Algorithms for maximum independent set”, Journal of Algorithms, Vol. 7, no. 3, pp. 425-440.
https://doi.org/10.1016/0196-6774(86)90032-5
20. Tarjan, R.E. and Trojanowski, A.E. (1977), “Finding a maximum independent set”, SIAM Journal on Computing, Vol. 6, pp. 537-546.
https://doi.org/10.1137/0206038
21. Moon, J.W. and Moser, L. (1965), “On cliques in graphs”, Israel J. Math., Vol. 3, pp. 23-28.
https://doi.org/10.1007/BF02760024
22. Pardalos, P.M. and Xue, J. (1994), “The maximum clique problem”, Journal of Global Optimization, Vol. 4, pp. 301-328.
https://doi.org/10.1007/BF01098364
23. Olemskoy, I.V. and Firyulina, O.S. (2014), “The algorithm for finding the largest independent set”, Vestnik, S.Pb. Universiteta, Ser. 10: Prikladnaya matematika, informatika, protsessy upravleniya, Iss. 1, pp. 81-91.
24. Plotnikov, A.D. (2012), “Heuristic algorithm for searching for the largest independent set”, Kibernetika i sistemnyi analiz, no. 5, pp. 41-48.
25. Listrovoy, S.V. (2014), “The method of enumeration of maximal independent sets in arbitrary non-oriented graphs”, Elektronnoe modelirovanie, Vol. 36, no. 1, pp. 3-17.
26. Listrovoy, S.V. and Minukhin, S.V. (2010), “General approach to solving optimization problems in distributed computing systems and theory of intelligence systems construction”, Journal of Automation and Information Sciences, Vol. 42, no. 3, pp. 30-46.
https://doi.org/10.1615/JAutomatInfScien.v42.i3.30
27. Listrovoy, S.V. and Minukhin, S.V. (2010), “A general approach to solving optimization problems in distributed computing systems and the theory of constructing intelligent systems”, Problemy upravleniya i informatiki, no. 2, pp.65-82.