Development of maximum clique definition method in a non-oriented graph

Authors

DOI:

https://doi.org/10.15587/1729-4061.2017.111056

Keywords:

cliques in non-oriented arbitrary graph, parallel computing methods

Abstract

The paper recommends the MCP solution method with small time complexity O(2n3log2n), that allows from one viewpoint solving such problems as definition of the maximum independent sets and minimum vertex covers in graphs, as well as isomorphism of graphs and isomorphic embedding, as far as all those problems may be converted within polynomial time into MCP. This set of problems is formal models of a wide range of management problems in rail transport information systems, and the solution thereof requires the algorithms for their realization with small time complexity. Therefore, the time complexity decrease is an actual task. In the paper, admissibility of decreasing the time complexity of the suggested procedure A for solving MCP is based on using the subsidiary procedure B for defining the estimates of the largest graph clique values, and on its basis the method of the problem solution is described in the paper as procedure A. Procedure A allows forming the cliques on the base of each vertex of graph i. As the process of clique formation on the base of each vertex may be independent, then procedure A may be effectively vectorized. It makes possible in case of using processing cells for solving the MCP to decrease the time complexity of its operation to O(2n2log2n), and the mentioned complex of the problems will be solved in a real-time scale. 

Author Biographies

Sergey Listrovoy, Ukrainian State University of Railway Transport Feierbakh sq., 7, Kharkiv, Ukraine, 61050

Doctor of Technical Sciences, Professor

Department of specialized computer systems

Volodymyr Butenko, Ukrainian State University of Railway Transport Feierbakh sq., 7, Kharkiv, Ukraine, 61050

PhD, Associate Professor

Department of specialized computer systems

Volodymyr Bryksin, Ukrainian State University of Railway Transport Feierbakh sq., 7, Kharkiv, Ukraine, 61050

PhD, Senior Lecturer

Department information technologies

Oleksandra Golovko, Ukrainian State University of Railway Transport Feierbakh sq., 7, Kharkiv, Ukraine, 61050

PhD, Associate Professor

Department of Computer Engineering and Control Systems

References

  1. Butenko, V. M. (2008). Yakist informatsiyno-vymiriuvalnykh system na zaliznychnomu transporti Ukrainy. Zb. naukov. prats. UkrDAZT, 99, 151–155.
  2. Boynik, A. B., Zagariy, G. I., Koshevoy, S. V. et. al. (2008). Diagnostirovanie ustroystv zheleznodorozhnoy avtomatiki i agregatov podvizhnyh edinic. Kharkiv: ChP Izdatel'stvo “Novoe slovo”, 304.
  3. Listrovyi, S. V., Panchenko, S. V., Moiseienko, V. I., Butenko, V. M. (2017). Matematychne modeliuvannia v rozpodilenykh informatsiino-keruiuchykh systemakh zaliznychnoho transportu. Kharkiv: FOP Brovin O.V., 220.
  4. Listrovoy, S. V., Minuhin, S. V., Listrovaya, E. S. (2015). Monitoring distributed computing systems on the basis of the determined shortest paths and shortest hamiltonian cycles in a graph. Eastern-European Journal of Enterprise Technologies, 6 (4 (78)), 32–45. doi: 10.15587/1729-4061.2015.56247
  5. San Segundo, P., Lopez, A., Pardalos, P. M. (2016). A new exact maximum clique algorithm for large and massive sparse graphs. Computers & Operations Research, 66, 81–94. doi: 10.1016/j.cor.2015.07.013
  6. El Mouelhi, A., Jégou, P., Terrioux, C., Zanuttini, B. (2013). Some New Tractable Classes of CSPs and Their Relations with Backtracking Algorithms. Lecture Notes in Computer Science, 61–76. doi: 10.1007/978-3-642-38171-3_5
  7. Zhang, S., Wang, J., Wu, Q., Zhan, J. (2014). A fast genetic algorithm for solving the maximum clique problem. 2014 10th International Conference on Natural Computation (ICNC). doi: 10.1109/icnc.2014.6975933
  8. San Segundo, P., Matia, F., Rodriguez-Losada, D., Hernando, M. (2011). An improved bit parallel exact maximum clique algorithm. Optimization Letters, 7 (3), 467–479. doi: 10.1007/s11590-011-0431-y
  9. Bykova, V. (2012). The Clique Minimal Separator Decomposition of a Hypergraph. J. of Siberian Federal University. Mathematics Physics, 5 (1), 36–45.
  10. Bykova, V., Illarionov, R. (2014). On CLIQUE Problem for Sparse Graphs of Large Dimension. Information Technologies and Mathematical Modelling, 69–75. doi: 10.1007/978-3-319-13671-4_9
  11. Minukhin, S. (2012). Efficient method for single machine total tardiness problem. 2012 IV International Conference “Problems of Cybernetics and Informatics” (PCI). doi: 10.1109/icpci.2012.6486283
  12. Buchanan, A., Walteros, J. L., Butenko, S., Pardalos, P. M. (2014). Solving maximum clique in sparse graphs: An O(nm+n2d/4) algorithm for d-degenerate graphs. Optimization Letters, 8 (5), 1611–1617. doi: 10.1007/s11590-013-0698-2
  13. Veremyev, A., Prokopyev, O. A., Butenko, S., Pasiliao, E. L. (2015). Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs. Computational Optimization and Applications, 64 (1), 177–214. doi: 10.1007/s10589-015-9804-y
  14. Listrovoy, S. V., Tretiak, V. F., Listrovaya, A. S. (1999). Parallel algorithms of calculation process optimization for the Boolean programming problems. Engineering Simulation, 16, 569–579.

Downloads

Published

2017-10-30

How to Cite

Listrovoy, S., Butenko, V., Bryksin, V., & Golovko, O. (2017). Development of maximum clique definition method in a non-oriented graph. Eastern-European Journal of Enterprise Technologies, 5(4 (89), 12–17. https://doi.org/10.15587/1729-4061.2017.111056

Issue

Vol. 5 No. 4 (89) (2017): MATHEMATICS AND CYBERNETICS - APPLIED ASPECTS

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2017 Sergey Listrovoy, Volodymyr Butenko, Volodymyr Bryksin, Oleksandra Golovko

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.