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

  • Authors

    • S. V. Listrovoy
    • O. V. Golovko
    • V. M. Butenko
    • M. V. Ushakov
    • . .
    2018-09-15
    https://doi.org/10.14419/ijet.v7i4.3.19807
  • cliques in non-oriented graph, cost optimization tools, maximum clique problem, railway infrastructure, safety of control systems

  • 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.

     

     

  • References

    1. [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, http://dx.doi.org/10.1016/j.ijrmhm.2017.07.006

      [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, http://dx.doi.org/10.15587/1729-4061.2017.102005

      [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, http://dx.doi.org/10.15587/1729-4061.2016.76103

      [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, http://dx.doi.org/10.1007/s10559-017-9979-6

      [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, http://dx.doi.org/10.15587/1729-4061.2017.111056

      [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, http://dx.doi.org/10.1016/j.trpro.2016.05.482

      [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. http://dx.doi.org/10.15587/1729-4061.2017.92203 .

      [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, http://dx.doi.org/10.15587/1729-4061.2015.54496

      [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, http://dx.doi.org/10.1155/2015/783917

      [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. http://dx.doi.org/10.7307/ptt.v25i4.337

      [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, http://dx.doi.org/10.15587/1729-4061.2017.103220

      [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), https://doi.org/10.1051/matecconf/201711601013

      [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, http://dx.doi.org/10.29354/diag/83009

  • Downloads

  • How to Cite

    V. Listrovoy, S., V. Golovko, O., M. Butenko, V., V. Ushakov, M., & ., . (2018). Formulation of the Problem of Maximum Clique Determination in Non-Oriented Graphs. International Journal of Engineering & Technology, 7(4.3), 293-297. https://doi.org/10.14419/ijet.v7i4.3.19807

    Received date: 2018-09-18

    Accepted date: 2018-09-18

    Published date: 2018-09-15