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

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

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



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






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


Тр. Ин-та матем., 2017, том 25, номер 1, страницы 62–81 (Mi timb269)  

Взвешенная задача о покрытии $k$-цепей последовательно-параллельного графа

В. В. Лепин

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

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

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


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

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

Образец цитирования: В. В. Лепин, “Взвешенная задача о покрытии $k$-цепей последовательно-параллельного графа”, Тр. Ин-та матем., 25:1 (2017), 62–81

Цитирование в формате AMSBIB
\RBibitem{Lep17}
\by В.~В.~Лепин
\paper Взвешенная задача о покрытии $k$-цепей последовательно-параллельного графа
\jour Тр. Ин-та матем.
\yr 2017
\vol 25
\issue 1
\pages 62--81
\mathnet{http://mi.mathnet.ru/timb269}


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

    ОТПРАВИТЬ: 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
  • Труды Института математики
    Просмотров:
    Эта страница:110
    Полный текст:48
    Литература:11

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