Geodesic
Multicriterial graph problems with MAXMIN criterion
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 5, pp. 3-10 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

$r$-Criterial problems for $r$-weighted graphs are considered $(r\geq2)$. Certain kinds of subgraphs are called admissible. To solve problem means to choose a Pareto optimal admissible subgraph from the complete set of alternatives (CSA). The main result of this paper is following. Suppose that a criterion, denoted by MAXMIN, requires maximization of the minimal first edges' weight of the admissible subgraph and there is an effective procedure constructing the CSA for a $(r-1)$-criterial problem without this MAXMIN criterion. Then the CSA for the initial $r$-criterial problem is created effectively. Bibliogr. 11.
Keywords: admissible subgraph, indicator of subgraph's quality, Pareto optimal subgraph. 
@article{DA_2011_18_5_a0,
     author = {V. G. Vizing},
     title = {Multicriterial graph problems with {MAXMIN} criterion},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--10},
     year = {2011},
     volume = {18},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_5_a0/}
}
TY  - JOUR
AU  - V. G. Vizing
TI  - Multicriterial graph problems with MAXMIN criterion
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 3
EP  - 10
VL  - 18
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_5_a0/
LA  - ru
ID  - DA_2011_18_5_a0
ER  - 
%0 Journal Article
%A V. G. Vizing
%T Multicriterial graph problems with MAXMIN criterion
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 3-10
%V 18
%N 5
%U http://geodesic.mathdoc.fr/item/DA_2011_18_5_a0/
%G ru
%F DA_2011_18_5_a0
V. G. Vizing. Multicriterial graph problems with MAXMIN criterion. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 5, pp. 3-10. http://geodesic.mathdoc.fr/item/DA_2011_18_5_a0/

[1] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979, 536 pp. | MR

[2] Vizing V. G., “Ob odnoi dvukhkriterialnoi zadache na grafakh”, Diskret. analiz i issled. opratsii, 16:5 (2009), 34–40 | MR

[3] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Nauka, M., 1990, 384 pp. | MR | Zbl

[4] Emelichev V. A., Perepelitsa V. A., “Mnogokriterialnye zadachi ob ostovakh grafa”, Dokl. AN SSSR, 298:3 (1988), 544–547 | MR | Zbl

[5] Emelichev V. A., Perepelitsa V. A., “Slozhnost diskretnykh mnogokriterialnykh zadach”, Diskret. matematika, 6:1 (1994), 3–33 | MR | Zbl

[6] Zykov A. A., Osnovy teorii grafov, Vuz. kn., M., 2004, 663 pp.

[7] Kofman A., Vvedenie v teoriyu nechëtkikh mnozhestv, Radio i svyaz, M., 1982, 432 pp. | MR

[8] Sergienko I. V., Perepelitsa V. A., “K probleme nakhozhdeniya mnozhestv alternativ v diskretnykh mnogokriterialnykh zadachakh”, Kibernetika, 1987, no. 5, 85–93 | MR | Zbl

[9] Emelichev V. A., Perepeliza V. A., “Complexity of vector optimization problems on graphs”, Optimization, 22:6 (1991), 903–918 | MR | Zbl

[10] Kruskal J. B. (jr.), “On the shortest spanning subtree of a graph and the traveling salesman problem”, Proc. Amer. Math. Soc., 7:1 (1956), 48–50 | DOI | MR | Zbl

[11] Prim R. C., “Shortest connection networks and some generalizations”, Bell Syst. Techn., 36 (1957), 1389–1401