|
Известия высших учебных заведений. Математика, 2005, номер 12, страницы 11–14
(Mi ivm1136)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
О сложности задачи размещения на линии с ограничениями на минимальные расстояния
Г. Г. Забудский Омский филиал Института математики им. С. Л. Соболева СО РАН
Аннотация:
Изучается задача размещения взаимосвязанных прямоугольных объектов на линии с минимальной суммарной стоимостью связей и ограничениями на минимальные расстояния. Доказано, что задача является $NP$-трудной, если структура связей между объектами является либо корневым деревом, либо графом последовательно-параллельного типа и полиномиально разрешима для цепи.
Поступила: 01.09.2005
Образец цитирования:
Г. Г. Забудский, “О сложности задачи размещения на линии с ограничениями на минимальные расстояния”, Изв. вузов. Матем., 2005, № 12, 11–14; Russian Math. (Iz. VUZ), 49:12 (2005), 9–12
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ivm1136 https://www.mathnet.ru/rus/ivm/y2005/i12/p11
|
Статистика просмотров: |
Страница аннотации: | 246 | PDF полного текста: | 145 | Список литературы: | 52 | Первая страница: | 1 |
|