Optimal parallel algorithms for forest and term matching

Zvi M. Kedem, Krishna V. Palem

Research output: Contribution to journalArticlepeer-review

Abstract

Forest matching is a fundamental step in solving various problems defined on terms such as term matching. We describe the first optimal speedup parallel algorithm for solving the forest matching problem. Our algorithm runs in time O(log n) using n log n processors on a CRCW PRAM, given a forest of n nodes as input. We use this algorithm to design the first optimal speedup parallel algorithm for solving the term matching problem. We also extend these algorithms to run on the weaker CREW PRAM with optimal speedup as well. This will involve a simple randomization scheme for simulating concurrent writes through a use of hashing.

Original languageEnglish (US)
Pages (from-to)245-264
Number of pages20
JournalTheoretical Computer Science
Volume93
Issue number2
DOIs
StatePublished - Feb 17 1992

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimal parallel algorithms for forest and term matching'. Together they form a unique fingerprint.

Cite this