Линейный алгоритм минимальной перестройки структурстатьяИсследовательская статья
Статья опубликована в журнале из списка RSCI Web of Science
Информация о цитировании статьи получена из
Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 23 января 2020 г.
Аннотация:Предлагается линейный по времени и используемой памяти алгоритм, строящий минимальную последовательность операций, которая преобразует одну структуру (ориентированный граф из циклов и цепей) в другую. Структуры в такой последовательности могут иметь переменное множество ребер, список операций фиксирован и включает удаление и вставку участка структуры. Приводится полное доказательство точности алгоритма, т.е. того, что он находит соответствующий минимум. === URL: http://mi.mathnet.ru/ppi2228