VLSI Algorithms and Architectures: 3rd Aegean Workshop on Computing, AWOC 88 Corfu, Greece, June 28 – July 1, 1988 Proceedings

Parallel algorithms for evaluating sequences of set-manipulation operations....Pages 1-10
Fast parallel and sequential algorithms for edge-coloring planar graphs....Pages 11-23
Optimal parallel algorithms on planar graphs....Pages 24-32
Efficient parallel triconnectivity in logarithmic time....Pages 33-42
Subtree isomorphism is in random NC....Pages 43-52
All graphs have cycle separators and planar directed depth-first search is in DNC....Pages 53-63
On some languages in NC....Pages 64-73
O(log(n)) parallel time finite field inversion....Pages 74-80
Deterministic parallel list ranking....Pages 81-90
Optimal parallel algorithms for expression tree evaluation and list ranking....Pages 91-100
Optimal parallel evaluation of tree-structured computations by raking (extended abstract)....Pages 101-110
On finding lowest common ancestors: Simplification and parallelization....Pages 111-123
A scheduling problem arising from loop parallelization on MIMD machines....Pages 124-133
Scheduling dags to minimize time and communication....Pages 134-138
Computing a perfect matching in a line graph....Pages 139-148
Separation pair detection....Pages 149-159
Graph embeddings 1988: Recent breakthroughs, new directions....Pages 160-169
Simulating binary trees on hypercubes....Pages 170-180
Embedding rectangular grids into square grids....Pages 181-190
Efficient reconfiguration of VLSI arrays....Pages 191-200
Embedding grids into hypercubes....Pages 201-211
Compaction on the torus....Pages 212-225
Channel routing with short wires....Pages 226-236
Simple three-layer channel routing algorithms....Pages 237-246
Applying the classification theorem for finite simple groups to minimize pin count in uniform permutation architectures....Pages 247-256
A new algorithm for wiring layouts....Pages 257-267
Input sensitive VLSI layouts for graphs of arbitrary degree....Pages 268-277
Fast self-reduction algorithms for combinatorial problems of VLSI design....Pages 278-287
Regular structures and testing: RCC-adders....Pages 288-300
Parallel simulation and test of VLSI array logic....Pages 301-311
Universal hashing in VLSI....Pages 312-318
Converting affine recurrence equations to quasi-uniform recurrence equations....Pages 319-328
Better computing on the anonymous ring....Pages 329-338
Network complexity of sorting and graph problems and simulating CRCW PRAMS by interconnection networks....Pages 339-350
Analysis of a distributed scheduler for communication networks....Pages 351-360
Weighted distributed match-making....Pages 361-368
A tradeoff between information and communication in broadcast protocols....Pages 369-379
Families of consensus algorithms....Pages 380-390
Uniform self-stabilizing rings....Pages 391-400
The complexity of selection resolution, conflict resolution and maximum finding on multiple access channels....Pages 401-410
Optimal routing algorithms for mesh-connected processor arrays....Pages 411-422
Routing and sorting on mesh-connected arrays....Pages 423-433
Time lower bounds for parallel sorting on a mesh-connected processor array....Pages 434-443
A correction network for N-sorters....Pages 444-455
Cubesort: An optimal sorting algorithm for feasible parallel computers....Pages 456-464
A 4d channel router for a two layer diagonal model....Pages 465-476