Please use this identifier to cite or link to this item: http://lib.kart.edu.ua/handle/123456789/14725
Full metadata record
DC FieldValueLanguage
dc.contributor.authorListrovoy, Sergey-
dc.contributor.authorButenko, Volodymyr-
dc.contributor.authorBryksin, Volodymyr-
dc.contributor.authorGolovko, Oleksandra-
dc.date.accessioned2023-04-22T07:42:10Z-
dc.date.available2023-04-22T07:42:10Z-
dc.date.issued2017-
dc.identifier.citationListrovoy S. Development of maximum clique definition method in a non-oriented graph / S. Listrovoy, V. Butenko, V. Bryksin, О. Golovko // Eastern-European Journal of Enterprise Technologies. - 2017. - Vol. 5, № 4(89). - С. 12-17.uk_UA
dc.identifier.issn1729-3774 (print); 1729-4061 (online)-
dc.identifier.urihttp://lib.kart.edu.ua/handle/123456789/14725-
dc.description.abstractEN: 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.uk_UA
dc.description.abstractUA: Наведені результати теоретичних досліджень пошуку найбільшої кліки на прикладі оптимізації інформаційних систем залізничного транспорту. У більшості аналогічних розробок не описана можливість реалізації подібних методів для паралельних обчислень. Розроблений метод пошуку найбільшої кліки в довільному неорієнтованому графі з часовою складністю O(2n(n2log2n+n))≈O(2n3log2n) і малою похибкою. Ця розробка перспективна для складання алгоритмів паралельної обробки даних.-
dc.language.isoenuk_UA
dc.publisherТехнологічний центрuk_UA
dc.relation.ispartofseriesMathematics and Cybernetics - applied aspects;-
dc.subjectcliques in non-oriented arbitrary graphuk_UA
dc.subjectparallel computing methodsuk_UA
dc.subjectкліки в довільному неорієнтованому графі-
dc.subjectмаксимальні кліки-
dc.subjectметоди для паралельних обчислень-
dc.titleDevelopment of maximum clique definition method in a non-oriented graphuk_UA
dc.title.alternativeРозробка методу визначення максимальних клік в неорієнтованих графах-
dc.typeArticleuk_UA
Appears in Collections:2017

Files in This Item:
File Description SizeFormat 
Listrovoy.pdf323.8 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.