zbMATH — the first resource for mathematics

Multicriterial graph problems with MAXMIN criterion. (Russian) Zbl 1249.90303
Summary: $$r$$-criterial problems for $$r$$-weighted graphs are considered ($$r\geq 2$$). Certain types of subgraphs are called admissible. To solve the problem means to choose a Pareto optimal admissible subgraph from the complete set of alternatives (CSA). The main result of this paper is the following. Suppose that a criterion, denoted by MAXMIN, requires maximization of the minimal weight of the first edges of an admissible subgraph and that there is an effective procedure constructing the CSA for an $$(r-1)$$-criterial problem without this MAXMIN criterion. Then the CSA for the initial $$r$$-criterial problem is created effectively.

MSC:
 90C35 Programming involving graphs or networks