talk on June 1, 2026
4 views
Skip to first unread message
Nikolay Vereshchagin
May 26, 2026, 10:29:53 AMMay 26
to Kolmogorov seminar on complexity
On June 1st, 2026 at 18:30 (Moscow time), 17:30 (Paris time) we will have a talk by K. Gorbunov and V.A. Lubetsky (in Russian) on the distance between binary trees
Zoom link:
К. Горбунов, В.А. Любецкий "Расстояние между бинарными
деревьями и эволюция одного дерева относительно другого".
MAF-расстояние между двумя корневыми бинарными деревьями с
разметкой листьев одним и тем же множеством имён определяется
как минимальное число частей, на которые можно разрезать
оба дерева так, чтобы эти части были попарно изоморфны.
Доказано, что это расстояние вычисляется алгоритмом
квадратичного времени, который допускает
мультипликативную ошибку не более 2.
Доказательство основано на вложении одного дерева в
другое. Наш алгоритм принципиально отличается, как и
доказательство, от известных,
и проще других, которые основаны на теории двойственности
в линейном программировании.
деревьями и эволюция одного дерева относительно другого".
MAF-расстояние между двумя корневыми бинарными деревьями с
разметкой листьев одним и тем же множеством имён определяется
как минимальное число частей, на которые можно разрезать
оба дерева так, чтобы эти части были попарно изоморфны.
Доказано, что это расстояние вычисляется алгоритмом
квадратичного времени, который допускает
мультипликативную ошибку не более 2.
Доказательство основано на вложении одного дерева в
другое. Наш алгоритм принципиально отличается, как и
доказательство, от известных,
и проще других, которые основаны на теории двойственности
в линейном программировании.
Reply all
Reply to author
Forward
0 new messages