An approach to determination of maximal cliques in undirected graphs
Автор: S.V. Listrovoy, A.V. Sidorenko, E.S. Listrovaya
Журнал: International Journal of Modern Education and Computer Science @ijmecs
Статья в выпуске: 1 vol.10, 2018 года.
Бесплатный доступ
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.
Мaximal independent set, click, vertex cover, decomposition of a graph into triangles
Короткий адрес: https://sciup.org/15016725
IDR: 15016725 | DOI: 10.5815/ijmecs.2018.01.01
Список литературы An approach to determination of maximal cliques in undirected graphs
- Kann, V., On the Approximability of NP-Complete Optimization Problems, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, Sweden, 1992.
- John W. Raymond and Peter Willett. Maximum Common Subgraph Isomorphism Algorithms Matching Chemical Structures Journal of Computer-Aided Molecular Design, 16: 521–533, 2002
- Cone, M., Venkataraghavan, R. and McLafferty, F., J. Am. Chem. Soc., 99 (1977) 7668.
- Barrow, H. and Burstall, R., Inf. Proc. Lett., 4 (1976) 83.
- Raymond, J., Gardiner, E. and Willett, P., Comput. J., in the press.
- McGregor, J., Software Pract. Exper., 12 (1982) 23.
- Wong, A. and Akinniyi, F., Proc. Int. Conf. Systems, Man and Cybern., Bombay & New Delhi, India, 1983, pp. 197.
- Brown, R.D., Jones, G., Willett, P. and Glen, R., J. Chem. Inf. Comput. Sci., 34 (1994) 63.
- Funabiki, N. and Kitamichi, J., IEICE Trans. Inf. &Syst., E82-D (1999) 1145.
- 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.
- Detecting highly overlapping community structure by greedy clique expansion / C. Lee, F. Reid, A. McDaid, N. Hurley // Arxiv preprint arXiv:1002.1827. _ 2010.
- 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.
- 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.
- 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.
- Listrovoy S.V. On Correlation of Р And NP Classes // I.J.Modern Education and Computer Science, 2012, 3, 21-27.
Статья научная
