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.

90C35 Programming involving graphs or networks