AN EXACT QUADRATIC ALGORITHM FOR THE SHORTEST TREE TRANSFORMATION
The article proposes a new exact quadratic algorithm in complexity that solves the problem of the shortest transformation (“alignment”) of one loaded tree into another, taking into account arbitrary prices of operations on trees. Three operations are considered: adding vertex deletions to an edge or root of a tree and shifting a subtree with deletions.
Authors
- K. Yu. Gorbunov (ORCID: https://orcid.org/0000-0001-5438-6939)
- Vassily Lyubetsky (ORCID: https://orcid.org/0000-0002-3739-9161)
Institutions
- Lomonosov Moscow State University (RU)
- Institute for Information Transmission Problems (RU)
- Moscow State University (TJ)
Publication Details
- Journal
- Доклады Российской академии наук Математика информатика процессы управления
- Published
- 2024-12-15
- DOI
- https://doi.org/10.31857/s2686954324050058
- Primary Topic
- Algorithms and Data Compression
- Type
- article
- Field-Weighted Citation Impact
- 0.00