VLSI Algorithms and Architectures -

. .

Résumé :
From the Foreword: The papers in this volume were presented at the Aegean Workshop on Computing: VLSI Algorithms and Architectures (AWOC 88), organized by the Computer Technology Institute in Patras in cooperation with ACM, EATCS, IEEE and the General Secretariat of Research and Technology (Ministry of Industry, Energy & technology of Greece). They were selected from 119 abstracts submitted in response to the program committee's call for papers and to additional invitations from John Reif. AWOC 88 took place in Corfu, Greece, June 28-July 1, 1988. AWOC 88 is the third meeting in the International Workshop on Parallel Computing & VLSI series; the first meeting took place in Amalfi, Italy, 1984, and the second at Loutraki, Greece, 1986.

Sommaire:
Parallel algorithms for evaluating sequences of set-manipulation operations.- Fast parallel and sequential algorithms for edge-coloring planar graphs.- Optimal parallel algorithms on planar graphs.- Efficient parallel triconnectivity in logarithmic time.- Subtree isomorphism is in random NC.- All graphs have cycle separators and planar directed depth-first search is in DNC.- On some languages in NC.- O(log(n)) parallel time finite field inversion.- Deterministic parallel list ranking.- Optimal parallel algorithms for expression tree evaluation and list ranking.- Optimal parallel evaluation of tree-structured computations by raking (extended abstract).- On finding lowest common ancestors: Simplification and parallelization.- A scheduling problem arising from loop parallelization on MIMD machines.- Scheduling dags to minimize time and communication.- Computing a perfect matching in a line graph.- Separation pair detection.- Graph embeddings 1988: Recent breakthroughs, new directions.- Simulating binary trees on hypercubes.- Embedding rectangular grids into square grids.- Efficient reconfiguration of VLSI arrays.- Embedding grids into hypercubes.- Compaction on the torus.- Channel routing with short wires.- Simple three-layer channel routing algorithms.- Applying the classification theorem for finite simple groups to minimize pin count in uniform permutation architectures.- A new algorithm for wiring layouts.- Input sensitive VLSI layouts for graphs of arbitrary degree.- Fast self-reduction algorithms for combinatorial problems of VLSI design.- Regular structures and testing: RCC-adders.- Parallel simulation and test of VLSI array logic.- Universal hashing in VLSI.- Converting affine recurrence equations to quasi-uniform recurrence equations.- Better computing on the anonymous ring.- Network complexity of sorting and graph problems and simulating CRCW PRAMS by interconnection networks.- Analysis of a distributed scheduler for communication networks.- Weighted distributed match-making.- A tradeoff between information and communication in broadcast protocols.- Families of consensus algorithms.- Uniform self-stabilizing rings.- The complexity of selection resolution, conflict resolution and maximum finding on multiple access channels.- Optimal routing algorithms for mesh-connected processor arrays.- Routing and sorting on mesh-connected arrays.- Time lower bounds for parallel sorting on a mesh-connected processor array.- A correction network for N-sorters.- Cubesort: An optimal sorting algorithm for feasible parallel computers.- A 4d channel router for a two layer diagonal model.