@inproceedings{0734f88e9820479688067111ade91da3,
title = "Covering tree with stars",
abstract = "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.",
keywords = "NP-completeness, dynamic programming, graph algorithms, tree edit distance",
author = "Jan Baumbach and Jiong Guo and Rashid Ibragimov",
year = "2013",
doi = "10.1007/978-3-642-38768-5\_34",
language = "English",
isbn = "9783642387678",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "373--384",
booktitle = "Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings",
note = "19th International Computing and Combinatorics Conference, COCOON 2013 ; Conference date: 21-06-2013 Through 21-06-2013",
}