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

DOI:

https://doi.org/10.14419/ijet.v7i4.3.19807

Published:

2018-09-15

Keywords:

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] 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

View Full Article:

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

License

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution Licensethat allows others to share the work with an acknowledgement of the work''s authorship and initial publication in this journal.

    1. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal''s published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  1. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Received 2018-09-18
Accepted 2018-09-18
Published 2018-09-15