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

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

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



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






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


Дискретн. анализ и исслед. опер., сер. 1, 2006, том 13, номер 1, страницы 3–15 (Mi da20)  

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

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

А. А. Агеевa, В. П. Ильевb, А. В. Кононовa, А. С. Талевнинb

a Институт математики им. С. Л. Соболева СО РАН
b Омский государственный университет им. Ф. М. Достоевского

Аннотация: Исследуется вычислительная сложность известной задачи аппроксимации графов. Показано, что различные варианты этой задачи являются NP-трудными как для неориентированных, так и для ориентированных графов. Для одного варианта задачи доказано существование полиномиальной приближённой схемы.
Библ. 14.

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

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

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

УДК: 519.8
Статья поступила: 20.09.2005

Образец цитирования: А. А. Агеев, В. П. Ильев, А. В. Кононов, А. С. Талевнин, “Вычислительная сложность задачи аппроксимации графов”, Дискретн. анализ и исслед. опер., сер. 1, 13:1 (2006), 3–15; J. Appl. Industr. Math., 1:1 (2007), 1–8

Цитирование в формате AMSBIB
\RBibitem{AgeIleKon06}
\by А.~А.~Агеев, В.~П.~Ильев, А.~В.~Кононов, А.~С.~Талевнин
\paper Вычислительная сложность задачи аппроксимации графов
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2006
\vol 13
\issue 1
\pages 3--15
\mathnet{http://mi.mathnet.ru/da20}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2258900}
\zmath{https://zbmath.org/?q=an:1249.68085}
\transl
\jour J. Appl. Industr. Math.
\yr 2007
\vol 1
\issue 1
\pages 1--8
\crossref{https://doi.org/10.1134/S1990478907010012}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-67849127188}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da20
  • http://mi.mathnet.ru/rus/da/v13/s1/i1/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. Ильев В.П., Ильева С.Д., “3-приближенный алгоритм для одного варианта задачи аппроксимации графа”, Вестн. Омского ун-та, 54:4 (2009), 77–79
    2. В. П. Ильев, С. Д. Ильева, “Приближенные алгоритмы аппроксимации графами с ограниченным числом компонент”, Тр. Ин-та матем., 18:1 (2010), 47–52  mathnet
    3. В. П. Ильев, С. Д. Ильева, А. А. Навроцкая, “Приближённые алгоритмы для задач аппроксимации графов”, Дискретн. анализ и исслед. опер., 18:1 (2011), 41–60  mathnet  mathscinet  zmath; V. P. Il'ev, S. D. Il'eva, A. A. Navrotskaya, “Approximation algorithms for graph approximation problems”, J. Appl. Industr. Math., 5:4 (2011), 569–581  crossref
    4. В. П. Ильев, А. А. Навроцкая, “Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера”, ПДМ, 2011, № 3(13), 80–84  mathnet
    5. В. А. Баранский, М. Ю. Выплов, В. П. Ильев, “Минимизация модулярных и супермодулярных функций на $L$-матроидах”, Известия Иркутского государственного университета. Серия Математика, 4:3 (2011), 42–53  mathnet
    6. В. П. Ильев, С. Д. Ильева, А. А. Навроцкая, “О задаче кластеризации графа с ограничением на размеры кластеров”, Дискретн. анализ и исслед. опер., 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
    7. Р. Ю. Симанчёв, “О неравенствах, порождающих фасеты комбинаторных многогранников”, Дискретн. анализ и исслед. опер., 24:4 (2017), 95–110  mathnet  crossref  elib; R. Yu. Simanchev, “On facet-inducing inequalities for combinatorial polytopes”, J. Appl. Industr. Math., 11:4 (2017), 564–571  crossref
    8. Berger A., Grigoriev A., Winokurow A., “A Ptas For the Cluster Editing Problem on Planar Graphs”, Approximation and Online Algorithms (Waoa 2016), Lecture Notes in Computer Science, 10138, eds. Jansen K., Mastrolilli M., Springer International Publishing Ag, 2017, 27–39  crossref  mathscinet  zmath  isi  scopus
    9. А. В. Ильев, В. П. Ильев, “Об одной задаче кластеризации графа с частичным обучением”, ПДМ, 2018, № 42, 66–75  mathnet  crossref
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:351
    Полный текст:219
    Литература:37
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019