Titlebook: VLSI Algorithms and Architectures; 3rd Aegean Workshop John H. Reif Conference proceedings 1988 Springer-Verlag New York 1988 VLSI.communi

ovation

VLSI Algorithms and Architectures978-0-387-34770-7Series ISSN 0302-9743 Series E-ISSN 1611-3349

吗啡

Deterministic parallel list ranking,In this paper we describe a simple parallel algorithm for list ranking. The algorithm is deterministic and runs in .(log .) time on EREW P-RAM with ./log . processor. The algorithm matches the performance of the Cole-Vishkin [CV86a] algorithm but is simple and has reasonable constant factors.

万神殿

Scheduling dags to minimize time and communication,We study the complexity of a generalization of the unit-execution-time multiprocessor scheduling problem under precedence constraints, in which the number of communication arcs is also minimized. Most versions of the problem are shown NP-complete, and two polynomial algorithms are presented for specialized cases.

doxazosin

Graph embeddings 1988: Recent breakthroughs, new directions,The past few years have seen a number of results on graph embeddings that deserve to be called . because of their settling hard open problems and/or their raising important issues that promise to alter the direction of subsequent research on graph embeddings. We describe and discuss several such results.

CHAR

Lecture Notes in Computer Sciencehttp://image.papertrans.cn/v/image/980077.jpg

badinage

https://doi.org/10.1007/BFb0040367VLSI; communication; complexity; interconnect; logic; simulation

Ovulation

Parallel algorithms for evaluating sequences of set-manipulation operations,ery operation in . and returning the resulting set). We show that the problem of evaluating . 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.

anesthesia

Cursory

Deference

Optimal parallel algorithms for expression tree evaluation and list ranking, parallel algorithmic technique for computations on trees; it yields the first ./log . processor, .(log .) time deterministic parallel algorithm for expression tree evaluation, and solves many other tree problems within the same complexity bounds.