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.
| Originalsprog | Engelsk |
|---|---|
| Titel | Computing and Combinatorics : 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013. Proceedings |
| Redaktører | Ding-Zhu Du, Guochuan Zhang |
| Antal sider | 12 |
| Forlag | Springer |
| Publikationsdato | 2013 |
| Sider | 373-384 |
| ISBN (Trykt) | 978-3-642-38767-8 |
| ISBN (Elektronisk) | 978-3-642-38768-5 |
| DOI | |
| Status | Udgivet - 2013 |
| Begivenhed | 19th International Conference on Computing and Combinatorics - Hangzhou, Kina Varighed: 21. jun. 2013 → 23. jun. 2013 Konferencens nummer: 19 |
Konference
| Konference | 19th International Conference on Computing and Combinatorics |
|---|---|
| Nummer | 19 |
| Land/Område | Kina |
| By | Hangzhou |
| Periode | 21/06/2013 → 23/06/2013 |
| Navn | Lecture Notes in Computer Science |
|---|---|
| Vol/bind | 7936 |
| ISSN | 0302-9743 |
Emneord
- dynamic programming graph algorithms NP-completeness tree edit distance