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

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

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



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






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


ПДМ, 2011, номер 3(13), страницы 80–84 (Mi pdm336)  

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

Прикладная теория графов

Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера

В. П. Ильев, А. А. Навроцкая

Омский государственный университет им. Ф. М. Достоевского, г. Омск, Россия

Аннотация: В работе рассматриваются новые варианты задачи аппроксимации графа, в которых имеются ограничения на размер компонент связности аппроксимирующих графов. Доказано, что если мощность каждой компоненты аппроксимирующего графа не больше заданного целого числа $p\geq3$, то задача аппроксимации графа является $NP$-трудной, а в случае $p=2$ она полиномиально разрешима.

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

Полный текст: PDF файл (562 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 519.1

Образец цитирования: В. П. Ильев, А. А. Навроцкая, “Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера”, ПДМ, 2011, № 3(13), 80–84

Цитирование в формате AMSBIB
\RBibitem{IleNav11}
\by В.~П.~Ильев, А.~А.~Навроцкая
\paper Вычислительная сложность задачи аппроксимации графами с~компонентами связности ограниченного размера
\jour ПДМ
\yr 2011
\issue 3(13)
\pages 80--84
\mathnet{http://mi.mathnet.ru/pdm336}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm336
  • http://mi.mathnet.ru/rus/pdm/y2011/i3/p80

    ОТПРАВИТЬ: 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. В. П. Ильев, С. Д. Ильева, А. А. Навроцкая, “О задаче кластеризации графа с ограничением на размеры кластеров”, Дискретн. анализ и исслед. опер., 23:3 (2016), 5–20  mathnet  crossref  mathscinet  elib; V. P. Il'ev, S. D. Il'eva, A. A. Navrotskaya, “Graph clustering with a constraint on cluster sizes”, J. Appl. Industr. Math., 10:3 (2016), 341–348  crossref
    2. А. В. Ильев, В. П. Ильев, “Об одной задаче кластеризации графа с частичным обучением”, ПДМ, 2018, № 42, 66–75  mathnet  crossref
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:172
    Полный текст:66
    Литература:18
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019