Covering tree with stars

Jan Baumbach (), Jiong Guo () and Rashid Ibragimov ()
Additional contact information
Jan Baumbach: University of Southern Denmark
Jiong Guo: Universität des Saarlandes
Rashid Ibragimov: Max Planck Institute für Informatik

Journal of Combinatorial Optimization, 2015, vol. 29, issue 1, No 8, 152 pages

Abstract: 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 $$\mathcal {S}$$ S of stars, can we connect the stars in $$\mathcal {S}$$ 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 $$O(|V(T)|^2\cdot k\cdot |V(\mathcal{S})|^{2k})$$ O ( | V ( T ) | 2 · k · | V ( S ) | 2 k ) time.

Keywords: Graph algorithms; Tree edit distance; NP-completeness; Dynamic programming (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9692-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:1:d:10.1007_s10878-013-9692-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9692-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().