𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Searching in Trees, Series-Parallel and Interval Orders

✍ Scribed by Faigle, U.; Lovász, L.; Schrader, R.; Turán, Gy.

Book ID
118174138
Publisher
Society for Industrial and Applied Mathematics
Year
1986
Tongue
English
Weight
1002 KB
Volume
15
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On Parallel Selection and Searching in P
On Parallel Selection and Searching in Partial Orders: Sorted Matrices
✍ R. Sarnath; Xin He 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 246 KB

rithm given by Cole [3] runs in O(log n log\* n) time on an EREW PRAM and in O(log n log\* n/log log n) time on a CRCW PRAM. Both algorithms perform O(n) operations. However, not much work has been done on parallel algorithms for constrained selection. The sequential algorithm in [5] is parallelizab

Scheduling Interval Ordered Tasks in Par
Scheduling Interval Ordered Tasks in Parallel
✍ Sivaprakasam Sunder; Xin He 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 148 KB

We present the first NC algorithm for scheduling n unit length tasks on m identical processors for the case where the precedence constraint is an interval order. Our algorithm runs on a priority concurrent read, concurrent write parallel Ž 2 . Ž 5 . Ž 3 . random access machine in O log n with O n pr