|
|
Дискретн. анализ и исслед. опер., 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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
А. Р. Ураков, Т. В. Тимеряев, “О двух задачах аппроксимации взвешенных графов и алгоритмах их решения”, ПДМ, 2013, № 3(21), 86–92
 -
Р. Ю. Симанчёв, И. В. Уразова, “О гранях многогранника задачи аппроксимации графа”, Дискретн. анализ и исслед. опер., 22:2 (2015), 86–101
 ; R. Yu. Simanchev, I. V. Urazova, “On the faces of the graph approximation problem polytope”, J. Appl. Industr. Math., 9:2 (2015), 283–291 -
В. П. Ильев, С. Д. Ильева, А. А. Навроцкая, “О задаче кластеризации графа с ограничением на размеры кластеров”, Дискретн. анализ и исслед. опер., 23:3 (2016), 5–20 ; 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
-
Р. Ю. Симанчёв, “О неравенствах, порождающих фасеты комбинаторных многогранников”, Дискретн. анализ и исслед. опер., 24:4 (2017), 95–110 ; R. Yu. Simanchev, “On facet-inducing inequalities for combinatorial polytopes”, J. Appl. Industr. Math., 11:4 (2017), 564–571
-
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
 -
А. В. Ильев, В. П. Ильев, “Об одной задаче кластеризации графа с частичным обучением”, ПДМ, 2018, № 42, 66–75
|
| Просмотров: |
| Эта страница: | 330 | | Полный текст: | 80 | | Литература: | 36 | | Первая стр.: | 8 |
|
Пользовательское соглашение