Publication:3992991
From MaRDI portal
zbMath0771.68015MaRDI QIDQ3992991
Wojciech Rytter, Alan M. Gibbons
Publication date: 23 January 1993
68Q25: Analysis of algorithms and problem complexity
68-02: Research exposition (monographs, survey articles) pertaining to computer science
68W15: Distributed algorithms
Related Items
Unnamed Item, OPTIMAL PARALLEL PREPROCESSING ALGORITHMS FOR TESTING WEAK VISIBILITY OF POLYGONS FROM SEGMENTS, parallel parsing from recurrence equations, Natural complexity, computational complexity and depth, TIME AND ENERGY OPTIMAL LIST RANKING ALGORITHMS ON THE k-CHANNEL BROADCAST COMMUNICATION MODEL WITH NO COLLISION DETECTION, On the complexity of the maximum biplanar subgraph problem, Parallel dynamics and computational complexity of the Bak-Sneppen model, Fast parallel heuristics for the job shop scheduling problem, Fast parallel algorithms for the maximum empty rectangle problem., A parallel algorithm for solving the coloring problem on trapezoid graphs, Counting the number of perfect matchings in \(K_{5}\)-free graphs, Optimal parallel algorithms on planar graphs, Parallel algorithms for a class of graphs generated recursively, The language intersection problem for non-recursive context-free grammars, Reliable computations on faulty EREW PRAM, Parallel tree-contraction and Fibonacci numbers, Optimal parallel execution of complete binary trees and grids into most popular interconnection networks, Efficient parallel algorithms for doubly convex-bipartite graphs, A simple randomized parallel algorithm for maximal f-matchings, The maximal \(f\)-dependent set problem for planar graphs is in NC, A parallel tree difference algorithm, Multilist layering: Complexity and applications, Fast recognition of deterministic cfl's with a smaller number of processors, A string-matching algorithm for the CREW PRAM, On the parallel recognition of unambiguous context-free languages, On the complexity of the recognition of parallel 2D-image languages, On optimal parallel computations for sequences of brackets, The parallel complexity of two problems on concurrency, Parallel \(LL\) parsing, Sorting roughly sorted sequences in parallel, Parallel construction of minimal suffix and factor automata, Quasilinear cellular automata, Sorting networks of logarithmic depth, further simplified, Boolean circuit programming: A new paradigm to design parallel algorithms, A class of problems efficiently solvable on mesh-connected computers including dynamic expression evaluation, On XRAM and PRAM models, and on data-movement-intensive problems, Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages, The bulk-synchronous parallel random access machine, Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays, Efficient parallel algorithms to test square-freeness and factorize strings, Data-movement-intensive problems: Two folk theorems in parallel computation revisited, Optimal parallel 3-coloring algorithm for rooted trees and its applications, Deciding whether graph \(G\) has page number one is in NC, The parallel complexity of coarsest set partition problems, A sublinear parallel algorithm for some dynamic programming problems, An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem, Observations on \(\log(n)\) time parallel recognition of unambiguous cfl's, On the complexity of the k-chain subgraph cover problem, Alphabet-independent optimal parallel search for three-dimensional patterns, The computational complexity of pattern formation, Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms, The computational complexity of the Lorentz lattice gas, An optimal parallel algorithm to convert a regular expression into its Glushkov automaton, Parallel on-line parsing in constant time per word, Parallel RAM algorithms for factorizing words, A theorem on permutation graphs with applications, Locality-preserving hash functions for general purpose parallel computation, On two-dimensional pattern matching by optimal parallel algorithms, An optimal sublinear time parallel algorithm for some dynamic programming problems, List-ranking on interconnection networks., Sorting and doubling techniques for set partitioning and automata minimization problems, Dense edge-disjoint embedding of complete binary trees in interconnection networks, Design of parallel algorithms for the single resource allocation problem, Robust algorithms for constructing strongly convex hulls in parallel., Improving the efficiency of parallel minimum spanning tree algorithms, Squares, cubes, and time-space efficient string searching, The parallel complexity of growth models, Stochastic modelling of diffusion equations on a parallel machine, The computational complexity of generating random fractals, Dense edge-disjoint embedding of complete binary trees in the hypercube, Speed and quality of collective decision making: Imperfect information processing, The balanced binary tree technique on mesh-connected computers, Efficiently Testing $$T$$-Interval Connectivity in Dynamic Graphs, Covering Polygons with Rectangles, A sequential sorting network analogous to the batcher merge, A TREE-HEIGHT HIERARCHY OF CONTEXT-FREE LANGUAGES, EFFICIENT HARDWARE ALGORITHMS FOR N CHOOSE K COUNTERS USING THE BITONIC MERGER, The quickest flow problem, A PARALLEL DEMAND-DRIVEN SIMULATION ALGORITHM FOR SIMD COMPUTERS
