Volume 16, No 5, 2009, P. 34-40
V. G. Vizing
On one twocriterial graph problem
It is supposed that each edge of a graph has two number characteristics: the length and the width. The sum of the lengths of the edges of a subgraph is called the length of the subgraph, the maximal width of the edges of subgraph is called the width of subgraph. The length of subgraph is a negative characteristic of subgraph, the width of subgraph is its positive characteristic. The certain kinds of subgraphs are called admissible. A two-criterial problem of searching a Pareto optimal admissible subgraph is considered.
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