A PARALLEL TREE DIFFERENCE ALGORITHM

Authors
SKILLICORN DB
Citation
Db. Skillicorn, A PARALLEL TREE DIFFERENCE ALGORITHM, Information processing letters, 60(5), 1996, pp. 231-235
Citations number
14
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
60
Issue
5
Year of publication
1996
Pages
231 - 235
Database
ISI
SICI code
0020-0190(1996)60:5<231:APTDA>2.0.ZU;2-2
Abstract
We describe a tree difference and edit sequence algorithm with expecte d sequential execution time O(nlogIogn) and expected parallel executio n time O(logn), for trees of size n. The algorithm assumes unique labe ls and permits operations only on leaves and frontier subtrees. Despit e this assumption, its application domain includes structured text and hypertext, and it is much faster than existing algorithms based on dy namic programming.