Formulation of the Problem of Maximum Clique Determination in Non-Oriented Graphs
Keywords:cliques in non-oriented graph, cost optimization tools, maximum clique problem, railway infrastructure, safety of control systems
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.
 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
 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
 IEC 61508-1:2010. Functional safety of electrical/electronic/programmable electronic safety-related systems. Part 1: General requirements, (2010).
 BS EN 50126-1:2017: Railway Applications. The Specification and Demonstration of Reliability, Availability, Maintainability and Safety (RAMS), Generic RAMS Process, (2017).
 BS EN 50128:2011: Railway Applications -Communications, signaling and processing systems. Software for Railway Control and Protection Systems, (2011).
 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
 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
 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
 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
 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 .
 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
 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
 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
 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
 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
 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
LicenseAuthors who publish with this journal agree to the following terms:
- 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.
- 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.
- 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).