## Abstract

We study the tree edit distance (TED) 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 S of stars, can we connect the stars in S 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 TED considered here is also NP-hard, even when both input trees have 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 (Formula presented.) time.

Original language | English |
---|---|

Pages (from-to) | 141-152 |

Number of pages | 12 |

Journal | Journal of Combinatorial Optimization |

Volume | 29 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2013 |

Externally published | Yes |

## Keywords

- Dynamic programming
- Graph algorithms
- NP-completeness
- Tree edit distance