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

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

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



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






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


Тр. Ин-та матем., 2011, том 19, номер 2, страницы 69–81 (Mi timb152)  

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

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

В. В. Лепин, О. И. Дугинов

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

Аннотация: Исследуются задачи нахождения бикликовой степени и бикликового числа графа $G$. Наименьшее число $bc(G)$ такое, что существует покрытие множества ребер графа $G$ не более $bc(G)$ полными двудольными графами (бикликами) называется бикликовым числом графа $G$. Наименьшее число $\eta(G)$ называется бикликовой степенью графа, если существует покрытие множества ребер графа бикликами, при котором каждая вершина покрыта не более чем $\eta(G)$ бикликами. Приведен алгоритм полиномиальной трудоемкости для нахождения бикликового покрытия с наименьшей бикликовой степенью и бикликового покрытия наименьшим числом биклик графа в классе графов с ограниченной путевой шириной.

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

Тип публикации: Статья
УДК: 519.1
Поступила в редакцию: 21.09.2011

Образец цитирования: В. В. Лепин, О. И. Дугинов, “Алгоритмы для нахождения покрытий бикликами графа с ограниченной путевой шириной”, Тр. Ин-та матем., 19:2 (2011), 69–81

Цитирование в формате AMSBIB
\RBibitem{LepDug11}
\by В.~В.~Лепин, О.~И.~Дугинов
\paper Алгоритмы для нахождения покрытий бикликами графа с~ограниченной путевой шириной
\jour Тр. Ин-та матем.
\yr 2011
\vol 19
\issue 2
\pages 69--81
\mathnet{http://mi.mathnet.ru/timb152}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/timb152
  • http://mi.mathnet.ru/rus/timb/v19/i2/p69

    ОТПРАВИТЬ: 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. В. В. Лепин, О. И. Дугинов, “О числе бикликового покрытия декартова произведения графов”, Тр. Ин-та матем., 21:1 (2013), 78–87  mathnet
    2. В. В. Лепин, О. И. Дугинов, “Задачи и инварианты, связанные с бикликами и мультикликами графа”, Тр. Ин-та матем., 21:2 (2013), 103–127  mathnet
    3. О. И. Дугинов, “Сложность задач покрытия графа наименьшим числом полных двудольных графов”, Тр. Ин-та матем., 22:1 (2014), 51–69  mathnet
  • Труды Института математики
    Просмотров:
    Эта страница:267
    Полный текст:119
    Литература:20

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019