Covering tree with stars

Jan Baumbach, Jiong Guo, Rashid Ibragimov

Research output: Contribution to journalJournal articleResearchpeer-review

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. © 2013 Springer-Verlag Berlin Heidelberg.
Original languageEnglish
JournalJournal of Combinatorial Optimization
Volume29
Issue number1
Pages (from-to)141-152
ISSN1382-6905
DOIs
Publication statusPublished - 2015

    Fingerprint

Cite this