Name
Abstract | ||
|---|---|---|
In this paper, we investigate several mapping kernels to count all of the mappings between two rooted labeled trees beyond ordered trees, that is, cyclically ordered trees such as biordered trees, cyclic-ordered trees and cyclic-biordered trees, and degree-bounded unordered trees. Then, we design the algorithms to compute a top-down mapping kernel, an LCA-preserving segmental mapping kernel, an LCA-preserving mapping kernel, an accordant mapping kernel and an isolated-subtree mapping kernel for biordered trees in O(nm) time and ones for cyclic-ordered and cyclic-biordered trees in O(nmdD) time, where n is the number of nodes in a tree, m is the number of nodes in another tree, D is the maximum value of the degrees in two trees and d is the minimum value of the degrees in two trees. Also we design the algorithms to compute the above kernels for degree-bounded unordered trees in O(nm) time. On the other hand, we show that the problem of computing label-preserving leaf-extended top-down mapping kernel and label-preserving bottom-up mapping kernel is #P-complete. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-662-48119-6_24 | Lecture Notes in Artificial Intelligence |
Field | DocType | Volume |
Kernel (linear algebra),Combinatorics,Mathematics | Conference | 9067 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
8 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kouichi Hirata | 1 | 130 | 32.04 |
| Tetsuji Kuboyama | 2 | 140 | 29.36 |
| Takuya Yoshino | 3 | 4 | 4.54 |