S.V. Listrovoy; A.V. Sidorenko; E.S. Listrovaya

An Approach to Determination of Maximal Cliques in Undirected Graphs

Full Text (PDF, 700KB), PP.1-12

Views: 0 Downloads: 0

Author(s)

S.V. Listrovoy ^1,* A.V. Sidorenko ² E.S. Listrovaya ³

1. S.V. Ukrainian State University of Railway Transport

2. Samsung Electronics Ukraine Company, LLC Samsung R & D Institute

3. National Aerospace University. N.E. Zhukovsky

* Corresponding author.

DOI: https://doi.org/10.5815/ijmecs.2018.01.01

Received: 9 Oct. 2017 / Revised: 2 Nov. 2017 / Accepted: 29 Nov. 2017 / Published: 8 Jan. 2018

Index Terms

Мaximal independent set, click, vertex cover, decomposition of a graph into triangles

Abstract

The article proposes the implicit exhaustive search procedure based on the triangle decomposition of graphs for determining the maximal clique in the arbitrary undirected graph G in polynomial time; it has allowed developing an exact algorithm for solving the problem with time complexity not exceeding , where is the number of vertices in the graph G.

Cite This Paper

S.V. Listrovoy, A.V. Sidorenko, E.S. Listrovaya, "An Approach to Determination of Maximal Cliques in Undirected Graphs", International Journal of Modern Education and Computer Science(IJMECS), Vol.10, No.1, pp. 1-12, 2018.DOI: 10.5815/ijmecs.2018.01.01

Reference

[1] Kann, V., On the Approximability of NP-Complete Optimization Problems, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, Sweden, 1992.

[2] John W. Raymond and Peter Willett. Maximum Common Subgraph Isomorphism Algorithms Matching Chemical Structures Journal of Computer-Aided Molecular Design, 16: 521–533, 2002

[3] Cone, M., Venkataraghavan, R. and McLafferty, F., J. Am. Chem. Soc., 99 (1977) 7668.

[4] Barrow, H. and Burstall, R., Inf. Proc. Lett., 4 (1976) 83.

[5] Raymond, J., Gardiner, E. and Willett, P., Comput. J., in the press.

[6] McGregor, J., Software Pract. Exper., 12 (1982) 23.

[7] Wong, A. and Akinniyi, F., Proc. Int. Conf. Systems, Man and Cybern., Bombay & New Delhi, India, 1983, pp. 197.

[8] Brown, R.D., Jones, G., Willett, P. and Glen, R., J. Chem. Inf. Comput. Sci., 34 (1994) 63.

[9] Funabiki, N. and Kitamichi, J., IEICE Trans. Inf. &Syst., E82-D (1999) 1145.

[10] Gribkov M., Alexeevski A., Ivanova D., Karyagina A., Spirin S. Life Core, program for classification of 3D structures of macromolecules // Biophysics (Moscow). 2004.Vol. 48. Suppl. 1. P. 157–166.

[11] Detecting highly overlapping community structure by greedy clique expansion / C. Lee, F. Reid, A. McDaid, N. Hurley // Arxiv preprint arXiv:1002.1827. _ 2010.

[12] Uncovering the overlapping community structure of complex networks in nature and society / G. Palla, I. Der.enyi, I. Farkas, T. Vicsek // Nature. 2005. _ V. 435, . 7043. _ P. 814–818.

[13] Litvinenko V.A. Adaptive algorithms of definition of extreme sets of graphs // Proceeding of the International Scientific Conferences «Intelligent System (IEEE AIS’03)» and «Intelligent CAD’s (CAD-2003)».Scientific publication in 3 volumes. – 2003. – Vol. 3. – C. 52.

[14] Listrovoy S.V. The method of enumeration of maximal independent sets in arbitrary non-oriented graphs // Electron. Modeling-2014-36-No.1-C.3-17.

[15] Listrovoy S.V. On Correlation of Р And NP Classes // I.J.Modern Education and Computer Science, 2012, 3, 21-27.

International Journal of Modern Education and Computer Science (IJMECS)