Volume 18, No 5, 2011, P. 3-10

UDC 519.718
V. G. Vizing
Multicriterial graph problems with maxmin criterion

Abstract:
r-Criterial problems for r-weighted graphs are considered (r ≥ 2). 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.

Vizing Vadym Georgievich ¹
1. Apt. 26, 18/2 Varnenskaya str., 65070 Odessa, Ukraine
e-mail: vizing@paco.net