scientific article

Publication date: 23 January 1993

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

parallel algorithms $P$-complete problems class $NC$efficient parallelisation

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Distributed algorithms (68W15)

Related Items (93)

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 ⋮ Dense edge-disjoint embedding of complete binary trees in the hypercube ⋮ A parallel algorithm for solving the coloring problem on trapezoid graphs ⋮ An optimal sublinear time parallel algorithm for some dynamic programming problems ⋮ EFFICIENT HARDWARE ALGORITHMS FOR N CHOOSE K COUNTERS USING THE BITONIC MERGER ⋮ The Power of Spreadsheet Computations ⋮ Speed and quality of collective decision making: Imperfect information processing ⋮ A parallel algorithm for edge-coloring partial k-trees ⋮ Efficient parallel computing with memory faults ⋮ An optimal parallel algorithm for computing a near-optimal order of matrix multiplications ⋮ Squares, cubes, and time-space efficient string searching ⋮ The balanced binary tree technique on mesh-connected computers ⋮ OPTIMAL PARALLEL PREPROCESSING ALGORITHMS FOR TESTING WEAK VISIBILITY OF POLYGONS FROM SEGMENTS ⋮ The parallel complexity of growth models ⋮ The language intersection problem for non-recursive context-free grammars ⋮ A class of problems efficiently solvable on mesh-connected computers including dynamic expression evaluation ⋮ Parallel $LL$ parsing ⋮ Stochastic modelling of diffusion equations on a parallel machine ⋮ 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 ⋮ Lower bounds for the matrix chain ordering problem ⋮ Efficiently Testing $$T$$-Interval Connectivity in Dynamic Graphs ⋮ Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition ⋮ Graph layout problems ⋮ Parallel recognition and ranking of context-free languages ⋮ The quickest flow problem ⋮ Fast deterministic simulation of computations on faulty parallel machines ⋮ Sub-cubic cost algorithms for the all pairs shortest path problem ⋮ List-ranking on interconnection networks. ⋮ The parallel complexity of elimination ordering procedures ⋮ The maximal f-dependent set problem for planar graphs is in NC ⋮ Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality ⋮ The computational complexity of generating random fractals ⋮ Sorting roughly sorted sequences in parallel ⋮ parallel parsing from recurrence equations ⋮ Parallel construction of minimal suffix and factor automata ⋮ Covering Polygons with Rectangles ⋮ TIME AND ENERGY OPTIMAL LIST RANKING ALGORITHMS ON THE k-CHANNEL BROADCAST COMMUNICATION MODEL WITH NO COLLISION DETECTION ⋮ 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 ⋮ 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 ⋮ Counting the number of perfect matchings in $K_{5}$-free graphs ⋮ From the theory to the tools: parallel dynamic programming ⋮ Deciding whether graph $G$ has page number one is in NC ⋮ The parallel complexity of coarsest set partition problems ⋮ Fast recognition of deterministic cfl's with a smaller number of processors ⋮ A string-matching algorithm for the CREW PRAM ⋮ A sublinear parallel algorithm for some dynamic programming problems ⋮ Computing parameters of sequence-based dynamic graphs ⋮ 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 maximum biplanar subgraph problem ⋮ Parallel dynamics and computational complexity of the Bak-Sneppen model ⋮ Optimal parallel algorithms on planar graphs ⋮ Parallel algorithms for a class of graphs generated recursively ⋮ Fast parallel heuristics for the job shop scheduling problem ⋮ Fast parallel algorithms for the maximum empty rectangle problem. ⋮ Quasilinear cellular automata ⋮ A sequential sorting network analogous to the batcher merge ⋮ Sorting networks of logarithmic depth, further simplified ⋮ Boolean circuit programming: A new paradigm to design parallel algorithms ⋮ 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 ⋮ A TREE-HEIGHT HIERARCHY OF CONTEXT-FREE LANGUAGES ⋮ 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 ⋮ 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. ⋮ Parallel on-line parsing in constant time per word ⋮ Natural complexity, computational complexity and depth ⋮ Improving the efficiency of parallel minimum spanning tree algorithms ⋮ 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 ⋮ A PARALLEL DEMAND-DRIVEN SIMULATION ALGORITHM FOR SIMD COMPUTERS ⋮ The parallel complexity of two problems on concurrency

This page was built for publication: