Algorithms and Methods for Solving Scheduling Problems and Other Extremum Problems on Large-Scale Graphs |
| |
Authors: | E V Pankratiev A M Chepovskiy E A Cherepanov S V Chernyshev |
| |
Institution: | (1) Moscow State University, Moscow, Russia;(2) Bauman Moscow State Technical University, Moscow, Russia |
| |
Abstract: | 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′ ⊂ 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.__________Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 9, No. 1, pp. 235–251, 2003. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|