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

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

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



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






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


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

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

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

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

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

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

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

Полный текст: PDF файл (222 kB)
Список литературы: PDF файл   HTML файл

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

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

Тип публикации: Статья
УДК: 519.2+621.391
Статья поступила: 03.12.2013
Переработанный вариант: 10.02.2014

Образец цитирования: А. А. Агеев, А. В. Кельманов, А. В. Пяткин, “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://www.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}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da780
  • http://mi.mathnet.ru/rus/da/v21/i4/p3

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. В. Кельманов, А. В. Пяткин, “О сложности некоторых квадратичных евклидовых задач 2-кластеризации”, Ж. вычисл. матем. и матем. физ., 56:3 (2016), 498–504  mathnet  crossref  elib; A. V. Kel'manov, A. V. Pyatkin, “On the complexity of some quadratic Euclidean 2-clustering problems”, Comput. Math. Math. Phys., 56:3 (2016), 491–497
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:265
    Полный текст:66
    Литература:64
    Первая стр.:35
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019