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

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

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



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






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


Тр. Ин-та матем., 2014, том 22, номер 1, страницы 51–69 (Mi timb208)  

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

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

О. И. Дугинов

Институт математики НАН Беларуси

Аннотация: Изучается вычислительная сложность и сложность аппроксимации задачи о наименьшем бикликовом покрытии вершин графа и задачи о наименьшем бикликовом покрытии ребер графа. Известно, что задачи $NP$-полны в классе двудольных графов. Установлено, что первая задача решается за полиномиальное время в классе $S_{1,2,3}$-свободных двудольных графов, где $S_{1,2,3}$ — граф с вершинами $a, b, c, d, e, f, g$ и ребрами $ab, bc, cd, fe, ed, gd.$ Показано, что первая задача в классе двудольных графов не аппроксимируется за полиномиальное время с гарантированной оценкой точности $k\ln n,$ где $0<k<0.25$ — константа, а $n$ — количество вершин в заданном графе (в предположении $P\ne NP$) и решается за полиномиальное время с гарантированной оценкой точности $H_n,$ где $H_n$ — $n$-я частичная сумма гармонического ряда. Доказана $NP$-полнота задачи о наименьшем бикликовом покрытии ребер графа в классе $(K_{3,4},K_{3,4}-e)$-свободных двудольных графов со степенью вершин не более 7.

Полный текст: PDF файл (649 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 519.1
Поступила в редакцию: 02.02.2014

Образец цитирования: О. И. Дугинов, “Сложность задач покрытия графа наименьшим числом полных двудольных графов”, Тр. Ин-та матем., 22:1 (2014), 51–69

Цитирование в формате AMSBIB
\RBibitem{Dug14}
\by О.~И.~Дугинов
\paper Сложность задач покрытия графа наименьшим числом полных двудольных графов
\jour Тр. Ин-та матем.
\yr 2014
\vol 22
\issue 1
\pages 51--69
\mathnet{http://mi.mathnet.ru/timb208}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/timb208
  • http://mi.mathnet.ru/rus/timb/v22/i1/p51

    ОТПРАВИТЬ: 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. В. В. Быкова, Ч. М. Монгуш, “Декомпозиционный подход к исследованию формальных контекстов”, ПДМ, 2019, № 44, 113–126  mathnet  crossref
  • Труды Института математики
    Просмотров:
    Эта страница:372
    Полный текст:153
    Литература:28
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020