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

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."

---

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."

---

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."
Content:
Front Matter....Pages -
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

---

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."
Content:
Front Matter....Pages -
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
....