Abstract | ||
---|---|---|
An anchored alignment tree between two rooted labeled trees with respect to a mapping that is a correspondence between nodes in two trees, called an anchoring, is an alignment tree which contains a node labeled by a pair of labels for every pair of nodes in the anchoring. In this paper, we formulate an anchored alignment problem as the problem, when two rooted labeled trees and an anchoring between them are given as input, to output an anchored alignment tree if there exists; to return "no" otherwise. Then, we show that the anchored alignment problem can be solved in O(h alpha(2) + n + m) time and in O(h alpha) space, where n is the number of nodes in a tree, m is the number of nodes in another tree, h is the maximum height of two trees and alpha is the cardinality of an anchoring. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1007/978-3-662-48119-6_22 | Lecture Notes in Artificial Intelligence |
Field | DocType | Volume |
Combinatorics,Anchoring,Cardinality,Mathematics | Conference | 9067 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
3 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yuma Ishizaka | 1 | 0 | 0.68 |
Takuya Yoshino | 2 | 4 | 4.54 |
Kouichi Hirata | 3 | 130 | 32.04 |