S.V. Listrovoy, A.V. Sidorenko, E.S. Listrovaya
Èlektron. model. 2017, 39(4):03-18
https://doi.org/10.15407/emodel.39.04.003
ABSTRACT
Based on the rank approach the authors propose a method of enumeration of maximum independent sets of nonoriented connected graph with time complexity that does not exceed, at an average, O (n6), where n is the number of vertices in the graph, for the graphs which do not contain separating vertices, which dimension does not exceed n=125.
KEYWORDS
maximal independent set, click, vertex cover.
REFERENCES
1. Merrifield, R.E. and Simmons, H.E. (1989), Topological methods in chemistry, New York, John Wiley & Sons, USA.
2. Hosoya, H. (1971),Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Jpn., Vol. 44, no. 9, pp. 2332-2339.
3. Miller, R.E. and Muller, D.E. (1960), The problem of the maximum consistent subsets, IBM Research Report RC-240, J. T. Watson Research Center, Yorktown Heights, New York, USA. Moon J.W., Moser L. On cliques in graphs, Israel J. Math.,Vol. 3, p. 23-28.
4. Watson J.T. Research Center, Yorktown Heights, N.Y. Moon J.W., Moser L. On cliques in graphs, Israel J. Math. Vol. 3, p. 23-28.
5. Harley, E., Bonner, A. and Goodman, N. (2001), Uniform integration of genome mapping data using intersection graphs, Bioinformatics, Vol. 17, pp. 487-494.
6. Moon, J.W. and Moser, L. (1965), On cliques in graphs, Israel J. Math., Vol. 3, pp. 23-28.
7. Tomita, E., Tanaka, A. and Takahashi, H. (2006), The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science, Vol. 363, pp. 28-42.
8. Prodinger, H. and Tichy, R.F. (1982), Fibonacci numbers of graphs, Fibonacci Quart, Vol. 20, no. 1, pp.16-21.
9. 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.
10. Listrovoy, S.V. and Minukhin, S.V. (2010), “A general approach to the solution of optimization problems in distributed computing systems and the theory of constructing intellectual systems”, Problemy upravleniya i informatika, no. 2, pp.65-82.
11. 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.
12. Listrovoy, S.V., Listrovaya, E.S., Panchenko, S.V., Moiseenko, V.I. and Kamenev, A.U. (2017), Mathematical models in computer control systems RAILWAYS and parallel computing: Monograph, FOP Brovin O., Kharkiv, Ukraine.