Covering tree with stars

Jan Baumbach; Jiong Guo; Rashid Ibragimov

doi:10.1007/s10878-013-9692-y

Covering tree with stars

Jan Baumbach, Jiong Guo, Rashid Ibragimov

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

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	https://doi.org/10.1007/s10878-013-9692-y
State	Published - Jan 2013
Externally published	Yes

Keywords

Dynamic programming
Graph algorithms
NP-completeness
Tree edit distance

Access to Document

10.1007/s10878-013-9692-y

Cite this

@article{30245c44ad194d02bd0353e8796fbc81,

title = "Covering tree with stars",

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.",

keywords = "Dynamic programming, Graph algorithms, NP-completeness, Tree edit distance",

author = "Jan Baumbach and Jiong Guo and Rashid Ibragimov",

note = "Publisher Copyright: {\textcopyright} 2013, Springer Science+Business Media New York.",

year = "2013",

month = jan,

doi = "10.1007/s10878-013-9692-y",

language = "English",

volume = "29",

pages = "141--152",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - Covering tree with stars

AU - Baumbach, Jan

AU - Guo, Jiong

AU - Ibragimov, Rashid

PY - 2013/1

Y1 - 2013/1

N2 - 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.

AB - 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.

KW - Dynamic programming

KW - Graph algorithms

KW - NP-completeness

KW - Tree edit distance

UR - http://www.scopus.com/inward/record.url?scp=84920614867&partnerID=8YFLogxK

U2 - 10.1007/s10878-013-9692-y

DO - 10.1007/s10878-013-9692-y

M3 - Article

AN - SCOPUS:84920614867

SN - 1382-6905

VL - 29

SP - 141

EP - 152

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 1

ER -

Covering tree with stars

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this