|
Эта публикация цитируется в 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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
В. П. Ильев, С. Д. Ильева, А. А. Навроцкая, “О задаче кластеризации графа с ограничением на размеры кластеров”, Дискретн. анализ и исслед. опер., 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 -
А. В. Ильев, В. П. Ильев, “Об одной задаче кластеризации графа с частичным обучением”, ПДМ, 2018, № 42, 66–75
|
Просмотров: |
Эта страница: | 201 | Полный текст: | 69 | Литература: | 19 | Первая стр.: | 1 |
|