Том 2, номер 4, 1995 г., Стр. 13-31

УДК 519.8
Э. Х. Гимади
Эффективные алгоритмы для решения многоэтапной задачи размещения на цепи

Аннотация:
Для NP-трудной многоэтапной сетевой задачи размещения построены алгоритмы решения в случае сети, представляющей собой цепь. Показано, что существует оптимальное решение рассматриваемой задачи (МЗРЦ) с совокупностью согласованно-связных областей обслуживания. Показано также, что в отличие от обычной (одноуровневой, простейшей) задачи размещения оптимального решения МРЗЦ с совокупностью центральных областей обслуживания может не существовать. Один из предложенных алгоритмов имеет полиномиальную оценку временной сложности, а другой (будучи неполиномиален в случае произвольного числа этапов) более эффективен для двух- и трехэтапной задач. 
Библиогр. 18. 

Гимади Э. X. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 8 августа 1995 г.