Geodesic
Algorithms and methods for solving scheduling problems and other extremum problems on large-scale graphs
Fundamentalʹnaâ i prikladnaâ matematika, Tome 9 (2003) no. 1, pp. 235-251 
E. V. Pankratiev; A. M. Chepovskii; E. A. Cherepanov; S. V. Chernyshev. Algorithms and methods for solving scheduling problems and other extremum problems on large-scale graphs. Fundamentalʹnaâ i prikladnaâ matematika, Tome 9 (2003) no. 1, pp. 235-251. http://geodesic.mathdoc.fr/item/FPM_2003_9_1_a13/
@article{FPM_2003_9_1_a13,
     author = {E. V. Pankratiev and A. M. Chepovskii and E. A. Cherepanov and S. V. Chernyshev},
     title = {Algorithms and methods for solving scheduling problems and other extremum problems on large-scale graphs},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {235--251},
     year = {2003},
     volume = {9},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2003_9_1_a13/}
}
TY  - JOUR
AU  - E. V. Pankratiev
AU  - A. M. Chepovskii
AU  - E. A. Cherepanov
AU  - S. V. Chernyshev
TI  - Algorithms and methods for solving scheduling problems and other extremum problems on large-scale graphs
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2003
SP  - 235
EP  - 251
VL  - 9
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/FPM_2003_9_1_a13/
LA  - ru
ID  - FPM_2003_9_1_a13
ER  - 
%0 Journal Article
%A E. V. Pankratiev
%A A. M. Chepovskii
%A E. A. Cherepanov
%A S. V. Chernyshev
%T Algorithms and methods for solving scheduling problems and other extremum problems on large-scale graphs
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2003
%P 235-251
%V 9
%N 1
%U http://geodesic.mathdoc.fr/item/FPM_2003_9_1_a13/
%G ru
%F FPM_2003_9_1_a13

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Kormen T., Leizerson Ch., Rivest R., Algoritmy: postroenie i analiz, MTsNMO, M., 1999

[2] Thorup M., “Undirected single-source shortest paths with positive integer weights in linear time”, Journal of the ACM, 46:3 (1999), 362–394 | DOI | MR | Zbl

[3] Williams J. W. J., “Heapsort”, Commun. ACM, 7:6 (1964), 347–348

[4] Inyukhin A. V., Pankratev E. V., Chepovskii A. M., Chernyshev S. V., “Ispolzovanie T-sistemy dlya preobrazovaniya grafa dorog v zadache optimizatsii marshrutov dvizheniya”, Vysokoproizvoditelnye vychisleniya i ikh prilozheniya, Trudy Vserossiiskoi nauchnoi konferentsii (30 oktyabrya–2 noyabrya 2000 g., g. Chernogolovka), Izd-vo Mosk. un-ta, M., 2000, 220–223

[5] Pankratev E. V., Chepovskii A. M., Cherepanov E. A., Chernyshev S. V., “Nakhozhdenie naborov optimalnykh marshrutov na bolshikh setkakh dorog geoinformatsionnykh sistem”, Problemy peredachi i obrabotki informatsii v setyakh i sistemakh telekommunikatsii, Materialy 10-i Mezhdunarodnoi nauch.-tekhn. konf., Ryazanskaya gosudarstvennaya radiotekhnicheskaya akademiya, Ryazan, 2001, 240–241