Volume 18, No 5, 2011, P. 310
UDC 519.718
V. G. Vizing
Multicriterial graph problems with maxmin criterion
Abstract:
rCriterial problems for rweighted 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 rcriterial problem is created effectively.
Bibliogr. 11.
Keywords: admissible subgraph, indicator of subgraph’s quality, Pareto optimal subgraph.
Vizing Vadym Georgievich ^{1}
1. Apt. 26, 18/2 Varnenskaya str., 65070 Odessa, Ukraine
email: vizing@paco.net
