Дискретный анализ и исследование операций
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Дискретный анализ и исследование операций, 2014, том 21, выпуск 4, страницы 3–11 (Mi da780)  
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)

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

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

a Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
b Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия
PDF полного текста (222 kB) Список цитирования (5)
Список литературы:
PDF
HTML
Аннотация: Рассматривается задача поиска разреза максимального веса в полном неориентированном графе, вершинами которого являются точки $q$-мерного пространства. Анализируются два случая, в которых длины рёбер равны (i) евклидовым расстояниям между точками пространства и (ii) квадратам этих расстояний. Доказано, что в обоих случаях задача NP-трудна в сильном смысле. Показано также, что для них в предположении $\mathrm{P\neq NP}$ не существует полностью полиномиальной приближённой схемы (FPTAS). Библиогр. 17.
Ключевые слова: граф, разрез, евклидово пространство, NP-трудная задача.
Статья поступила: 03.12.2013
Переработанный вариант: 10.02.2014
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2014, Volume 8, Issue 4, Pages 453–457
DOI: https://doi.org/10.1134/S1990478914040012
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.2+621.391
Образец цитирования: А. А. Агеев, А. В. Кельманов, А. В. Пяткин, “Cложность задачи о разрезе максимального веса в евклидовом пространстве”, Дискретн. анализ и исслед. опер., 21:4 (2014), 3–11; J. Appl. Industr. Math., 8:4 (2014), 453–457
Цитирование в формате AMSBIB
\RBibitem{AgeKelPya14}
\by А.~А.~Агеев, А.~В.~Кельманов, А.~В.~Пяткин
\paper Cложность задачи о~разрезе максимального веса в~евклидовом пространстве
\jour Дискретн. анализ и исслед. опер.
\yr 2014
\vol 21
\issue 4
\pages 3--11
\mathnet{http://mi.mathnet.ru/da780}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3289216}
\transl
\jour J. Appl. Industr. Math.
\yr 2014
\vol 8
\issue 4
\pages 453--457
\crossref{https://doi.org/10.1134/S1990478914040012}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da780
  • https://www.mathnet.ru/rus/da/v21/i4/p3
    • Эта публикация цитируется в следующих 5 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:454
    PDF полного текста:122
    Список литературы:88
    Первая страница:35
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024