期刊名称：Eastern-European Journal of Enterprise Technologies
印刷版ISSN：1729-3774
电子版ISSN：1729-4061
出版年度：2017
卷号：5
期号：4
页码：12-17
DOI：10.15587/1729-4061.2017.111056
语种：English
出版社：PC Technology Center
摘要：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.
关键词：cliques in non-oriented arbitrary graph;parallel computing methods
