Lecture Notes in Computer Science

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.