Линейный алгоритм перестройки графа

 
Код статьиS000523100002861-1-1
DOI10.31857/S000523100002861-1
Тип публикации Статья
Статус публикации Опубликовано
Авторы
Аффилиация: Институт проблем передачи информации им. А.А. Харкевича РАН
Адрес: Москва, Российская Федерация
Аффилиация:
Институт проблем передачи информации им. А.А. Харкевича РАН
Московский государственный университет им. М.В. Ломоносова
Адрес: Российская Федерация, Москва
Название журналаАвтоматика и телемеханика
ВыпускВыпуск 12
Страницы124-141
Аннотация

Предлагается линейный по времени и памяти алгоритм, который строит минимальную по суммарной цене последовательность операций, преобразующих любой данный ориентированный граф, у которого степень любой вершины не более двух, в любой данный такого же типа граф. Эта последовательность называется кратчайшей. Разрешены четыре стандартные операции переклейки графов с равной ценой и еще две дополнительные операции — вставки и удаления связного участка ребер, которые имеют равную между собой цену. Приводится доказательство того, что алгоритм находит минимум при этом ограничении на цены.

Ключевые словаграф, цикл, цепь, преобразование графа, цена операции, комбинаторная задача, оптимизация на графах, линейный алгоритм.
Получено04.12.2018
Дата публикации11.12.2018
Цитировать   Скачать pdf Для скачивания PDF необходимо авторизоваться
Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 315

Оценка читателей: голосов 0

1. Горбунов К.Ю., Любецкий В.А. Линейный алгоритм кратчайшей перестройки графов при разных ценах операций // Информац. процессы. 2016. Т. 16. № 2. C. 223–236.

2. Lyubetsky V.A., Gershgorin R.A., Seliverstov A.V., Gorbunov K.Yu. Algorithms for Reconstruction of Chromosomal Structures // BMC Bioinformatics. 2016. V. 17. P. 40.1–40.23.

3. Lyubetsky V.A., Gershgorin R.A., Gorbunov K.Yu. Chromosome Structures: Reduction of Certain Problems with Unequal Gene Content and Gene Paralogs to Integer Linear Programming // BMC Bioinformatics. 2017. V. 18. P. 537.1–537.18.

4. Braga M.D.V., Stoye J. Sorting Linear Genomes with Rearrangements and Indels // IEEE/ACM Trans. on Computational Biology and Bioinformatics. 2015. V. 12. No. 3. P. 1–13.

5. Yin Z., Tang J., Schaeffer S.W., Bader D.A. Exemplar or Matching: Modeling DCJ Problems with Unequal Content Genome Data // J. Combinatorial Optimization. 2016. V. 32. No. 4. P. 1165–1181.

6. Горбунов К.Ю., Любецкий В.А. Линейный алгоритм минимальной перестройки структур // Пробл. передачи информации. 2017. Т. 53. Вып. 1. С. 60–78.

Система Orphus

Загрузка...
Вверх