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

Abstract

EN: 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.

UA: Наведені результати теоретичних досліджень пошуку найбільшої кліки на прикладі оптимізації інформаційних систем залізничного транспорту. У більшості аналогічних розробок не описана можливість реалізації подібних методів для паралельних обчислень. Розроблений метод пошуку найбільшої кліки в довільному неорієнтованому графі з часовою складністю O(2n(n2log2n+n))≈O(2n3log2n) і малою похибкою. Ця розробка перспективна для складання алгоритмів паралельної обробки даних.