Analyzing Edit Distance on Trees: Tree Swap Distance is Intractable
2011 (English)In: Proceedings of the Prague Stringology Conference 2011 / [ed] Jan Holub and Jan Žďárek, Prague: Prague Stringology Club, Czech Technical University , 2011, 59-73 p.Conference paper (Refereed)
The string correction problem looks at minimal ways to modify one stringinto another using fixed operations, such as for example inserting a symbol, deleting asymbol and interchanging the positions of two symbols (a “swap”). This has been generalizedto trees in various ways, but unfortunately having operations to insert/deletenodes in the tree and operations that move subtrees, such as a “swap” of adjacent subtrees,makes the correction problem for trees intractable. In this paper we investigatewhat happens when we have a tree edit distance problem with only swaps. We callthis problem tree swap distance, and go on to prove that this correction problem isNP-complete. This suggests that the swap operation is fundamentally problematic inthe tree case, and other subtree movement models should be studied.
Place, publisher, year, edition, pages
Prague: Prague Stringology Club, Czech Technical University , 2011. 59-73 p.
formella språk, träd, omordning, komplexitet, NP.komplett
Research subject Computer and Information Science
IdentifiersURN: urn:nbn:se:umu:diva-54158ISBN: 978-80-01-04870-2OAI: oai:DiVA.org:umu-54158DiVA: diva2:516199
Prague Stringology Conference, August 29-31 2011, Prague