1 Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU 2 Computer Science, Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU 3 Universität des Saarlandes 4 Max Planck Institute für Informatik 5 Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU
We study the tree edit distance problem with edge deletions and edge insertions as edit operations. We reformulate a special case of this problem as Covering Tree with Stars (CTS): given a tree T and a set of stars, can we connect the stars in by adding edges between them such that the resulting tree is isomorphic to T? We prove that in the general setting, CST is NP-complete, which implies that the tree edit distance considered here is also NP-hard, even when both input trees having diameters bounded by 10. We also show that, when the number of distinct stars is bounded by a constant k, CTS can be solved in polynomial time by presenting a dynamic programming algorithm running in time. © 2013 Springer-Verlag Berlin Heidelberg.
Journal of Combinatorial Optimization, 2015, Vol 29, Issue 1, p. 141-152
Main Research Area: