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

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

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



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






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


Дискретн. анализ и исслед. опер., 2011, том 18, номер 3, страницы 84–88 (Mi da656)  

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

Анализ влияния числа рёбер в связных графах на трудоёмкость решения задачи о независимом множестве

Д. С. Малышевab

a Национальный исследовательский университет "Высшая школа экономики" (Нижегородский филиал), Нижний Новгород, Россия
b Нижегородский гос. университет, Нижний Новгород, Россия

Аннотация: Изучается сложностной статус задачи о независимом множестве в классах связных графов, определяемых функциональными ограничениями числа рёбер от числа вершин. Показано, что для любого натурального $C$ в классе графов $\bigcup_{n=1}^\infty\{G\mid|V(G)|=n$, $|E(G)|\leq n+C[\log_2(n)]\}$ эта задача полиномиально разрешима. С другой стороны, доказано, что она не является полиномиально разрешимой в классе графов $\bigcup_{n=1}^\infty\{G\mid|V(G)|=n, |E(G)|\leq n+f^2(n)\}$ для любой неограниченной неубывающей функции $f(n)\colon\mathbb N\to\mathbb N$, экспонента от которой растёт быстрее, чем полином от $n$. Последний результат справедлив, если для задачи о независимом множестве нет субэкспоненциальных алгоритмов. Библиогр. 3.

Ключевые слова: вычислительная сложность, задача о независимом множестве.

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

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

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

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

Образец цитирования: Д. С. Малышев, “Анализ влияния числа рёбер в связных графах на трудоёмкость решения задачи о независимом множестве”, Дискретн. анализ и исслед. опер., 18:3 (2011), 84–88; J. Appl. Industr. Math., 6:1 (2012), 97–99

Цитирование в формате AMSBIB
\RBibitem{Mal11}
\by Д.~С.~Малышев
\paper Анализ влияния числа р\"ебер в~связных графах на трудо\"емкость решения задачи о~независимом множестве
\jour Дискретн. анализ и исслед. опер.
\yr 2011
\vol 18
\issue 3
\pages 84--88
\mathnet{http://mi.mathnet.ru/da656}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2883750}
\zmath{https://zbmath.org/?q=an:1249.68089}
\transl
\jour J. Appl. Industr. Math.
\yr 2012
\vol 6
\issue 1
\pages 97--99
\crossref{https://doi.org/10.1134/S1990478912010103}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84857672145}


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

    ОТПРАВИТЬ: 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. Д. С. Малышев, “Влияние роста упаковочного числа графов на сложность задачи о независимом множестве”, Дискрет. матем., 25:2 (2013), 63–67  mathnet  crossref  mathscinet  elib; D. S. Malyshev, “The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem”, Discrete Math. Appl., 23:3-4 (2013), 245–249  crossref  elib
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:236
    Полный текст:45
    Литература:39
    Первая стр.:4
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019