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

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

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



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






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


Прикладная дискретная математика, 2011, номер 3(13), страницы 80–84 (Mi pdm336)  

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

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

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

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

Омский государственный университет им. Ф. М. Достоевского, г. Омск, Россия
Список литературы:
Аннотация: В работе рассматриваются новые варианты задачи аппроксимации графа, в которых имеются ограничения на размер компонент связности аппроксимирующих графов. Доказано, что если мощность каждой компоненты аппроксимирующего графа не больше заданного целого числа $p\geq3$, то задача аппроксимации графа является $NP$-трудной, а в случае $p=2$ она полиномиально разрешима.
Ключевые слова: аппроксимация графа, полиномиально разрешимая задача, $NP$-трудная задача.
Тип публикации: Статья
УДК: 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}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/pdm336
  • https://www.mathnet.ru/rus/pdm/y2011/i3/p80
  • Эта публикация цитируется в следующих 3 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика
    Статистика просмотров:
    Страница аннотации:307
    PDF полного текста:102
    Список литературы:41
    Первая страница:1
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024