Дерево, ближайшее в среднем к данному набору деревьевстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 24 января 2020 г.
Аннотация:Сформулирована задача построения дерева, ближайшего в среднем к данному набору деревьев. Понятие “ближайшее” сформулировано на основе представления о событиях, подсчет числа которых позволяет отличить каждое из данных деревьев от искомого дерева. Эти события называются дивергенцией, дупликацией, потерей, переносом; аналогично могут быть рассмотрены и другие списки событий. Предложен алгоритм, который решает эту задачу за кубическое время от размера исходных данных. Доказаны корректность алгоритма и кубическая оценка его сложности.