|
Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, 1979, Volume 19, Number 3, Pages 739–755
(Mi zvmmf5333)
|
|
|
|
A generalized “wave” method for solving extremal problems on graphs
S. M. Avdoshin, V. V. Belov Moskva
Abstract:
An optimization complex of a graph is constructed, and on the basis of this a statement is formalized in the class of wave subgraphs introduced in this paper also, and a solution of extremal problems on an arbitrary flow graph is given. The applicability of the method to the solution of multi-iteration problems is considered using the example of the problem of the greatest pair-combination of a bipartite graph. A new algorithm with an estimate of complexity improving the known estimate $O(n^{5/2})$ is presented.
Received: 10.02.1978 Revised: 29.11.1978
Citation:
S. M. Avdoshin, V. V. Belov, “A generalized “wave” method for solving extremal problems on graphs”, Zh. Vychisl. Mat. Mat. Fiz., 19:3 (1979), 739–755; U.S.S.R. Comput. Math. Math. Phys., 19:3 (1979), 189–207
Linking options:
https://www.mathnet.ru/eng/zvmmf5333 https://www.mathnet.ru/eng/zvmmf/v19/i3/p739
|
Statistics & downloads: |
Abstract page: | 306 | Full-text PDF : | 144 | First page: | 1 |
|