RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2014, том 21, выпуск 4, страницы 3–11 (Mi da780)

Эта публикация цитируется в 5 статьях

Cложность задачи о разрезе максимального веса в евклидовом пространстве

А. А. Агеевa, А. В. Кельмановab, А. В. Пяткинab

a Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
b Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия

Аннотация: Рассматривается задача поиска разреза максимального веса в полном неориентированном графе, вершинами которого являются точки $q$-мерного пространства. Анализируются два случая, в которых длины рёбер равны (i) евклидовым расстояниям между точками пространства и (ii) квадратам этих расстояний. Доказано, что в обоих случаях задача NP-трудна в сильном смысле. Показано также, что для них в предположении $\mathrm{P\neq NP}$ не существует полностью полиномиальной приближённой схемы (FPTAS). Библиогр. 17.

Ключевые слова: граф, разрез, евклидово пространство, NP-трудная задача.

УДК: 519.2+621.391

Статья поступила: 03.12.2013
Переработанный вариант: 10.02.2014


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2014, 8:4, 453–457

Реферативные базы данных:


© МИАН, 2024