| Article ID: | iaor19921932 |
| Country: | Germany |
| Volume: | 22 |
| Start Page Number: | 903 |
| End Page Number: | 918 |
| Publication Date: | Dec 1991 |
| Journal: | Optimization |
| Authors: | Emelicev V.A., Perepeliza V.A. |
| Keywords: | graphs |
The paper is dedicated to the computation complexity of multi-objective optimization problems on graphs. The classes of multi-objective problems with polynomial complexity or being polynomially reduced to be NP-hard are marked out. The unsolvability of a series of combinatorial multi-objective problems has been set up by means of linear convolution algorithm. The sufficient conditions under which these algorithms are statistically efficient have also been obtained.