Необходимо зарегистрироваться, чтобы получить доступ к полным текстам статей и выпусков журналов!
- Название статьи
- УЛУЧШЕННЫЙ АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО ОБЩЕГО ПОДДЕРЕВА СВЕРХУ ВНИЗ ДЛЯ ДВУХ НЕУПОРЯДОЧЕННЫХ КОРНЕВЫХ ДЕРЕВЬЕВ
- Авторы
- Кононов Дмитрий Сергеевич kds795@yandex.ru, эксперт, ЗАО «НПО "Эшелон"», Москва, Россия
- В разделе
- ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
- Ключевые слова
- деревья / изоморфизм / общие поддеревья / сложность / паросочетания / двудольный граф / задача о назначениях / деревья с атрибутами
- Год
- 2015 номер журнала 2 Страницы 16 - 24
- Индекс УДК
- 004.021
- Код EDN
- Код DOI
- Тип статьи
- Научная статья
- Аннотация
- Рассмотрены достигнутые на современном этапе результаты для решения задачи поиска максимального паросочетания двудольного графа и задач, сводимых к ней, в приложении для решения задачи поиска максимального общего поддерева сверху вниз для двух неупорядоченных корневых деревьев. Введены ряд эвристик, позволяющие сократить количество выполняемых операций в алгоритме поиска максимального общего поддерева сверху вниз для двух неупорядоченных корневых деревьев. Оценена сложность улучшенного алгоритма O(N2dmax), где N - порядок сравниваемых деревьев, а dmax - максимальная степень узлов, предыдущий лучший результат был O(N5/2). Данный результат был обобщен и на случай деревьев с атрибутами.
- Полный текст статьи
- Необходимо зарегистрироваться, чтобы получить доступ к полным текстам статей и выпусков журналов!
- Список цитируемой литературы
-
Gabriel V. Algorithms on Trees and Graphs. 1-е изд. - Берлин: Springer-Verlag, 2002. P. 211-224.
West D. B. Introduction to Graph Theory. 2-е изд. - Дели: Pearson Education, 2001. P. 143-186.
Algorithmic Solutions Software GmbH. Bipartite Weighted Matchings and Assignments (mwb_matching) // Library of Efficient Data types and Algorithms (LEDA). 1995. URL: http://www.algorithmic-solutions.info/leda_manual/mwb_matching.html (дата обращения: 4.10.2014).
Lyle R. R.E.T. A Weight-Scaling Algorithm for Min-Cost Imperfect Matchings in Bipartite Graphs // HP Laboratories. 2012. URL: http://www.hpl.hp.com/techreports/2012/HPL-2012-72.pdf (дата обращения: 12.09.2014).
Таха Х. А. Введение в исследование операций. 6-е изд. - М.: Вильямс, 2001. С. 206-213.
Bourgeois F. J.C.L. "An extension of the Munkres algorithm for the assignment problem to rectangular matrices" // Communications of the ACM. 1971. Vol. 14. No. 12. P. 802-804.
Volgenant J. B. "Solving the Rectangular assignment problem and applications" // Annals of Operations Research. 2010. Vol. 181. No. 1. P. 443-462.
Кормен Т. Алгоритмы. Построение и анализ. 3-е изд. - М.: Вильямс, 2013. С. 220-242.
Земляченко В. Н. Установление изоморфизма деревьев // Вопросы кибернетики. Москва. 1973. С. 54-60.
Dinitz Y. A.I.M.R., "On an algorithm of Zemlyachenco for subtree isomorthism" // Information Processing Letters. 1999. Vol. 70. No. 3. P. 141-146.
- Купить
