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

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

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



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






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


Дискретн. анализ и исслед. опер., 2011, том 18, номер 1, страницы 41–60 (Mi da637)  

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

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

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

a Омский гос. университет, Омск, Россия
b ООО "Омсктелеком", Омск, Россия

Аннотация: Рассматриваются несколько вариантов задачи аппроксимации графа. Предложены приближённые алгоритмы для этих задач, получены гарантированные оценки точности алгоритмов. В частности, показано, что задача аппроксимации графами с ограниченным числом компонент связности принадлежит классу APX. Ил. 1, библиогр. 12.

Ключевые слова: задача аппроксимации графа, приближённый алгоритм, гарантированная оценка точности.

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2011, 5:4, 569–581

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

Тип публикации: Статья
УДК: 519.8
Статья поступила: 20.07.2010
Переработанный вариант: 29.11.2010

Образец цитирования: В. П. Ильев, С. Д. Ильева, А. А. Навроцкая, “Приближённые алгоритмы для задач аппроксимации графов”, Дискретн. анализ и исслед. опер., 18:1 (2011), 41–60; J. Appl. Industr. Math., 5:4 (2011), 569–581

Цитирование в формате AMSBIB
\RBibitem{IleIleNav11}
\by В.~П.~Ильев, С.~Д.~Ильева, А.~А.~Навроцкая
\paper Приближ\"енные алгоритмы для задач аппроксимации графов
\jour Дискретн. анализ и исслед. опер.
\yr 2011
\vol 18
\issue 1
\pages 41--60
\mathnet{http://mi.mathnet.ru/da637}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2847828}
\zmath{https://zbmath.org/?q=an:1249.05366}
\transl
\jour J. Appl. Industr. Math.
\yr 2011
\vol 5
\issue 4
\pages 569--581
\crossref{https://doi.org/10.1134/S1990478911040120}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-82655189272}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da637
  • http://mi.mathnet.ru/rus/da/v18/i1/p41

    ОТПРАВИТЬ: 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. А. Р. Ураков, Т. В. Тимеряев, “О двух задачах аппроксимации взвешенных графов и алгоритмах их решения”, ПДМ, 2013, № 3(21), 86–92  mathnet
    2. Р. Ю. Симанчёв, И. В. Уразова, “О гранях многогранника задачи аппроксимации графа”, Дискретн. анализ и исслед. опер., 22:2 (2015), 86–101  mathnet  crossref  mathscinet  elib; R. Yu. Simanchev, I. V. Urazova, “On the faces of the graph approximation problem polytope”, J. Appl. Industr. Math., 9:2 (2015), 283–291  crossref
    3. В. П. Ильев, С. Д. Ильева, А. А. Навроцкая, “О задаче кластеризации графа с ограничением на размеры кластеров”, Дискретн. анализ и исслед. опер., 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
    4. Р. Ю. Симанчёв, “О неравенствах, порождающих фасеты комбинаторных многогранников”, Дискретн. анализ и исслед. опер., 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
    5. A. Berger, A. Grigoriev, A. Winokurow, “A ptas for the cluster editing problem on planar graphs”, Approximation and Online Algorithms (Waoa 2016), Lecture Notes in Computer Science, 10138, ed. K. Jansen, M. Mastrolilli, Springler, 2017, 27–39  crossref  mathscinet  zmath  isi  scopus
    6. А. В. Ильев, В. П. Ильев, “Об одной задаче кластеризации графа с частичным обучением”, ПДМ, 2018, № 42, 66–75  mathnet  crossref
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:330
    Полный текст:80
    Литература:36
    Первая стр.:8
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019