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

Аффилиация:
Институт проблем передачи информации им. А.А. Харкевича РАН
Московский государственный университет им. М.В. Ломоносова
Адрес: Российская Федерация, Москва

Название журнала

Автоматика и телемеханика

Выпуск

Выпуск 12

Страницы

124-141

Аннотация

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

Ключевые слова

граф, цикл, цепь, преобразование графа, цена операции, комбинаторная задача, оптимизация на графах, линейный алгоритм.

Получено

04.12.2018

Дата публикации

11.12.2018

Цитировать Скачать pdf Для скачивания PDF необходимо авторизоваться

ГОСТ	Горбунов К. Ю. , Любецкий В. А. Линейный алгоритм перестройки графа // Автоматика и телемеханика – 2018. – Выпуск 12 C. 124-141 [Электронный ресурс]. URL: http://ras.jes.su/ait/s000523100002861-1-1 (дата обращения: 09.10.2024). DOI: 10.31857/S000523100002861-1
MLA	Gorbunov, K., Lyubetsky, V. "A Linear Algorithm for Restructuring a Graph." Avtomatika i Telemekhanika 12 (2018):124-141. DOI: 10.31857/S000523100002861-1
APA	Gorbunov K., Lyubetsky V. (2018). A Linear Algorithm for Restructuring a Graph. Avtomatika i Telemekhanika (12), pp.124-141 DOI: 10.31857/S000523100002861-1

Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

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

Оценка читателей: голосов 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.