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'\subset 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.