Formulation of the Problem of Maximum Clique Determination in Non-Oriented Graphs

  • Abstract
  • Keywords
  • References
  • PDF
  • Abstract

    In the train traffic organization, large amount of information should be processed in real time. Thereby in complicated dispatching systems, rational use of resources is needed. To perform this work a model of a management system is constructed and it is represented as a sparse graph. Further optimization of the model requires solving the Maximum Clique Problem (MCP) for the less time than the exponential time. This article contains two procedures for solving the task for subexponential time. Procedure B accurately estimates the size of the maximum clique in the graph and performs the sorting of the vertices, in such a way that the vertices that are not exactly in the maximum clique can be rejected. Procedure A, in fact, finds cliques of the maximum size in a given graph, using the procedure B. The main advantage of this method is that using it is expedient in real time for sufficiently large graphs, which in turn is important for the construction of control systems.



  • Keywords

    cliques in non-oriented graph; cost optimization tools; maximum clique problem; railway infrastructure; safety of control systems

  • References

      [1] Gevorkyan E., Lavrynenko S., Ruckic M., Siemiatkowski Z., Kislitsa M, ”Ceramic cutting tools out of nanostructured refractory compounds”, International Journal of Refractory Metals and Hard Materials, Vol.68, (2017), pp:142–144,

      [2] Moiseenko V., Kameniev O., Gaievskyi V., “Predicting a technical condition of railway automation hardware under conditions of limited statistical data”, Eastern-European Journal of Enterprise Technologies, Vol.3, No.9 (88), (2017), pp.26–35,

      [3] IEC 61508-1:2010. Functional safety of electrical/electronic/programmable electronic safety-related systems. Part 1: General requirements, (2010).

      [4] BS EN 50126-1:2017: Railway Applications. The Specification and Demonstration of Reliability, Availability, Maintainability and Safety (RAMS), Generic RAMS Process, (2017).

      [5] BS EN 50128:2011: Railway Applications -Communications, signaling and processing systems. Software for Railway Control and Protection Systems, (2011).

      [6] Panchenko S., Siroklyn I., Lapko A., Kameniev A., Zmii S., “Improvement of the accuracy of determining movement parameters of cuts on classification humps by methods of video analysis”, Eastern-European Journal of Enterprise Technologies, Vol.4, Issue 3(82), (2016), pp.25–30,

      [7] Listrovaya E.S., Bryksin V.A., Kurtsev M.S., “Modeling Local Scheduler Operation Based on Solution of Nonlinear Boolean Programming Problems”, Cybernetics and Systems Analysis, Vol.53, No.5, (2017), pp.766–775,

      [8] Listrovoy S.V., Butenko V.M., Bryksin V.O., Golovko O.V., “Development of method of definition maximum clique in a non-oriented graph”, Eastern-European Journal of Enterprise Technologies, Vol.5, No.4 (89), (2017), pp.12–17,

      [9] Lomotko D.V., Alyoshinsky E.S., Zambrybor G.G., “Methodological Aspect of the Logistics Technologies Formation in Reforming Processes on the Railways”, Transportation Research Procedia, Vol.14, (2016), pp.2762-2766,

      [10] Panchenko S., Lavrukhin O., Shapatina O., “Creating a qualimetric criterion for the generalized level of vehicle”, Eastern-European Journal of Enterprise Technologies, Vol.1, No.3 (85), (2017), pp.39–45. .

      [11] Lomotko D.V., Kovalov A., Kovalova O., “Formation of fuzzy support system for decision-making on merchantability of rolling stock in its allocation”, Eastern-European Journal of Enterprise Technologies, Vol.6, No.3 (78), (2015), pp.11–17,

      [12] Wang Y., Sun H., Zhu J., Zhu B., “Optimization Model and Algorithm Design for Airline Fleet Planning in a Multiairline Competitive Environment”, Mathematical Problems in Engineering, Vol.2015, (2015), pp.1–13,

      [13] Najaf P., Famili S., “Application of an Intelligent Fuzzy Regression Algorithm in Road Freight Transportation Modelling”, Promet – Traffic&Transportation, Vol.25, No.4, (2013), Issue 4, pp.311–322.

      [14] Butko T.V., Prodaschuk S., Bogomazova G., Shelekhan G., Prodaschuk M., Purii R., “Improvement of technology for management of freight rolling stock on railway transport”, Eastern-European Journal Of Enterprise Technologies, No3(3), (2017), pp.4-11,

      [15] Pluhin O., Plugin A., Plugin D., Borziak O., Dudin O., “The effect of structural characteristics on electrical and physical properties of electrically conductive compositions based on mineral binders”, MATEC Web Conf., 6th International Scientific Conference “Reliability and Durability of Railway Transport Engineering Structures and Buildings” (Transbud-2017), Vol.116, (2017),

      [16] Plugin A., Trykoz L., Herasymenko O., Pluhin A., Konev V., “Independent diagnostic computer systems with the ability to restore operational characteristics of construction facilities”, Diagnostyka, Vol.19, No.2, (2018), pp.11-21,




Article ID: 19807
DOI: 10.14419/ijet.v7i4.3.19807

Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.