An exact quadratic algorithm for the shortest tree transformation

DOI10.1134/S1064562424702259MaRDI QIDQ7035199zbMATH OpenFDO

Authors Konstantin Yu. Gorbunov, Vassily Lyubetsky

Publication date 30 January 2025

Published in Doklady Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/S1064562424702259

zbMATH Keywords

discrete optimizationexact algorithmoperation costoperations on treequadratic-complexity algorithmshortest tree transformationtree alignment

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40) Programming involving graphs or networks (90C35)

Cites work

• Algorithms on Strings, Trees and Sequences
• Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)

This page was built for publication: An exact quadratic algorithm for the shortest tree transformation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7035199)