FUNDAMENTALNAYA I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2003, VOLUME 9, NUMBER 1, PAGES 235-251

Algorithms and methods for solving scheduling problems and other extremum problems on large-scale graphs

E. V. Pankratiev
A. M. Chepovskii
E. A. Cherepanov
S. V. Chernyshev

Abstract

View as HTML     View as gif image

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\text{'}$Ì 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\text{'}\; =\; (V\text{'},E\text{'})$ 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\text{'}$ are presented.

Location: http://mech.math.msu.su/~fpm/eng/k03/k031/k03114h.htm
Last modified: April 4, 2004.