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.