Downloads: 344

Files in This Item:
File Description SizeFormat 
j.tcs.2010.10.002.pdf182.42 kBAdobe PDFView/Open
Title: Exact algorithms for computing the tree edit distance between unordered trees
Authors: Akutsu, Tatsuya  kyouindb  KAKEN_id  orcid https://orcid.org/0000-0001-9763-797X (unconfirmed)
Fukagawa, Daiji
Takasu, Atsuhiro
Tamura, Takeyuki  kyouindb  KAKEN_id  orcid https://orcid.org/0000-0003-1596-901X (unconfirmed)
Author's alias: 阿久津, 達也
Keywords: Tree edit distance
Fixed-parameter algorithms
Dynamic programming
Unordered trees
Issue Date: 4-Feb-2011
Publisher: Elsevier B.V.
Journal title: Theoretical Computer Science
Volume: 412
Issue: 4-5
Start page: 352
End page: 364
Abstract: This paper presents a fixed-parameter algorithm for the tree edit distance problem for unordered trees under the unit cost model that works in O(2.62^k⋅poly(n)) time and O(n^2) space, where the parameter k is the maximum bound of the edit distance and n is the maximum size of input trees. This paper also presents polynomial-time algorithms for the case where the maximum degree of the largest common subtree is bounded by a constant
Rights: © 2010 Elsevier B.V.
This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
URI: http://hdl.handle.net/2433/149243
DOI(Published Version): 10.1016/j.tcs.2010.10.002
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.