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

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

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



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






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


Тр. Ин-та матем., 2016, том 24, номер 1, страницы 61–74 (Mi timb260)  

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

Решение взвешенной задачи о $k$-разделителе графа, имеющего особые модули

В. В. Лепин

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

Аннотация: Если дан граф $G$ с весовой функцией $\omega: V(G)\to\mathbb{R}^+,$ то весом подмножества вершин $U\subseteq V(G)$ называется $\omega(U)=\sum_{v\in U}\omega(v).$ Рассматривается задача нахождения наименьшего веса подмножества вершин $W$ такого, что каждая компонента $G-W$ имеет размер, не превосходящий $k.$ Представлен алгоритм, который решает эту задачу для графов обладающих особой модульной декомпозицией. Модулем графа $G$ называется множество вершин $M\subseteq V$ такое, что каждая вершина из $V\setminus M$ либо смежна со всеми вершинами из $M,$ либо ни с одной из них. Множество $V$ и каждое одновершинное множество называются тривиальными модулями. Если граф $G$ имеет только тривиальные модули, то он называется простым графом. Дан алгоритм, решающий эффективно взвешенную задачу о $k$-разделителе в классе графов, у которых все простые подграфы принадлежат множеству $\{P_4,\ldots,P_m\}\cup\{C_5,\ldots,C_m\}.$ Временная сложность алгоритма $O(n^2),$ где $n$ — число вершин графа. В классе кографов и последовательно-параллельных графов взвешенная задача о $k$-разделителе графа решается за линейное время.

Финансовая поддержка Номер гранта
Белорусский республиканский фонд фундаментальных исследований Ф15МЛД-022
Ф16РА-003
Работа выполнена при финансовой поддержке Белорусского республиканского фонда фундаментальных исследований (проекты Ф15МЛД-022 и Ф16РА-003).


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

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

Образец цитирования: В. В. Лепин, “Решение взвешенной задачи о $k$-разделителе графа, имеющего особые модули”, Тр. Ин-та матем., 24:1 (2016), 61–74

Цитирование в формате AMSBIB
\RBibitem{Lep16}
\by В.~В.~Лепин
\paper Решение взвешенной задачи о $k$-разделителе графа, имеющего особые модули
\jour Тр. Ин-та матем.
\yr 2016
\vol 24
\issue 1
\pages 61--74
\mathnet{http://mi.mathnet.ru/timb260}


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

    ОТПРАВИТЬ: 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. В. В. Лепин, “Взвешенная задача о покрытии $k$-цепей последовательно-параллельного графа”, Тр. Ин-та матем., 25:1 (2017), 62–81  mathnet
  • Труды Института математики
    Просмотров:
    Эта страница:138
    Полный текст:45
    Литература:15

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