| Presentation | 1996/1/26 A Parallel Algorithm for a Tree Distance Masahiro YAMAMOTO, Eiichi TANAKA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Several definitions and computing methods for the distance between rooted and ordered trees(RO-trees) were proposed. The strongly structure preserving distance (SSPD) is one of them. This paper describes a parallel algorithm for computing SSPD. The algorithm runs on the CREW PRAM model, and computes SSPD between RO-trees Tα and Tβ in time O(Nα+Nβ) with O ((NαNβ)/(Nα+Nβ)) proceccors, where Nα and Nβ are the numbers of vertices of the two trees. The space complexity is O(NαNβ). The cost of this algorithm is O(NαNβ), and is equal to the time complexity of a serial algorithm for computing SSPD. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | parallel algorithm / tree / distance / pattern matching / pattern recognition |
| Paper # | COMP95-73 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1996/1/26(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Parallel Algorithm for a Tree Distance |
| Sub Title (in English) | |
| Keyword(1) | parallel algorithm |
| Keyword(2) | tree |
| Keyword(3) | distance |
| Keyword(4) | pattern matching |
| Keyword(5) | pattern recognition |
| 1st Author's Name | Masahiro YAMAMOTO |
| 1st Author's Affiliation | Graduate School of Science and Technology, Kobe University() |
| 2nd Author's Name | Eiichi TANAKA |
| 2nd Author's Affiliation | Faculty of Engineering, Kobe University |
| Date | 1996/1/26 |
| Paper # | COMP95-73 |
| Volume (vol) | vol.95 |
| Number (no) | 498 |
| Page | pp.pp.- |
| #Pages | 10 |
| Date of Issue | |