ALGORITHMS AND METHODS FOR SOLVING SCHEDULING PROBLEMS AND OTHER EXTREMUM PROBLEMS ON LARGE-SCALE GRAPHS

摘要

We consider a large-scale directed graph G = (V, E) whose edges are endowed with a family of characteristics. A subset of vertices of the graph, V′ is contained in V, is selected and some additional conditions are imposed on these vertices. An algorithm for reducing the optimization problem on the graph G to an optimization problem on the graph G′ = (V′, E′) of a lower dimension is developed. The main steps of the solution and some methods for constructing an approximate solution to the problem on the transformed graph G′ are presented.