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

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

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



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






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


Тр. Ин-та матем., 2007, том 15, номер 1, страницы 78–90 (Mi timb86)  

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

Линейный алгоритм для нахождения максимального индуцированного паросочетания наименьшего веса в реберно-взвешенном дереве

В. В. Лепин

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

Аннотация: Индуцированным паросочетанием в графе $G$ называется множество ребер порожденного $1$-регулярного подграфа. Индуцированное паросочетание $M$ графа $G$ называется максимальным, если оно не содержится в индуцированном паросочетании с большим числом ребер. Предложен алгоритм, который задачу построения максимального индуцированного паросочетания наименьшего веса в реберно-взвешенном дереве решает за линейное время.
Библиогр. 21 назв.

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

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

Образец цитирования: В. В. Лепин, “Линейный алгоритм для нахождения максимального индуцированного паросочетания наименьшего веса в реберно-взвешенном дереве”, Тр. Ин-та матем., 15:1 (2007), 78–90

Цитирование в формате AMSBIB
\RBibitem{Lep07}
\by В.~В.~Лепин
\paper Линейный алгоритм для нахождения максимального индуцированного паросочетания наименьшего веса в реберно-взвешенном дереве
\jour Тр. Ин-та матем.
\yr 2007
\vol 15
\issue 1
\pages 78--90
\mathnet{http://mi.mathnet.ru/timb86}


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

    ОТПРАВИТЬ: 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_1,K_2\}$-упаковки наибольшего веса в графе”, Тр. Ин-та матем., 22:1 (2014), 78–97  mathnet
    2. В. В. Лепин, “Решение задачи о взвешенной независимой $\{K_1,K_2\}$-упаковке на графах с ограниченной древесной шириной”, Тр. Ин-та матем., 23:1 (2015), 98–114  mathnet
    3. В. В. Лепин, “Решение задачи о взвешенной независимой $\{K_1,K_2\}$-упаковке на графах со специальными блоками”, Тр. Ин-та матем., 23:2 (2015), 62–71  mathnet
  • Труды Института математики
    Просмотров:
    Эта страница:445
    Полный текст:197
    Литература:19

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