Parallel algorithms for evaluating sequences of set-manipulation operations | Zendy

Mikhail J. Atallah | Zendy; Michael T. Goodrich | Zendy; S. Rao Kosaraju | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Parallel algorithms for evaluating sequences of set-manipulation operations

Author(s) -

Mikhail J. Atallah,

Michael T. Goodrich,

S. Rao Kosaraju

Publication year - 1988

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/bfb0040368

Subject(s) - computer science , set (abstract data type) , sequence (biology) , algorithm , set operations , theoretical computer science , programming language , genetics , biology

Given an off-line sequence S of n set-manipulation operations, we investigate the parallel complexity of evaluating S (i.e. finding the response to every operation in S and returning the resulting set). We show that the problem of evaluating S is in NC for various combinations of common set-manipulation operations. Once we establish membership in NC (or, if membershp in NC is obvious), we develop techniques for improving the time and/or processor complexity.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research