EN|RU

Volume 18, No 4, 2011, P. 49-65

UDC 519.854
G. G. Zabudsky, A. Yu. Lagzdin
Polynomial algorithms for solving the quadratic bottleneck assignment problem on networks

Abstract:
The quadratic bottleneck assignment problem in terms of graphs is considered. The goal is to find permutation of the graph vertices on the network nodes that minimizes the cost between adjacent vertices. We provide polynomial algorithms for solving the problem on special networks.
Ill. 7, bibliogr. 13.

Keywords: quadratic bottleneck assignment problem, location problem, polynomial algorithm, graph.

Zabudsky Gennadiy Grigor'evich 1
Lagzdin ArtemYur'evich 1

1. Omsk department of S. L. Sobolev Institute of Mathematics, SB RAS,
13 Pevtsova str., 644099 Omsk, Russia
e-mail: zabudsky@o_m.oscsbras.ru, art.lagzdin@gmail.com

 © Sobolev Institute of Mathematics, 2015