scientific article
From MaRDI portal
Publication:4023519
zbMath0781.68009MaRDI QIDQ4023519
Publication date: 23 January 1993
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)
Related Items (only showing first 100 items - show all)
Coloring permutation graphs in parallel ⋮ \(O(\log n)\) numerical algorithms on a mesh with wormhole routing ⋮ Fringe analysis of synchronized parallel insertion algorithms in 2--3 trees. ⋮ An efficient parallel algorithm for the single function coarsest partition problem ⋮ A parallel algorithm for solving the coloring problem on trapezoid graphs ⋮ An insight on PRAM computational bounds ⋮ Two optimal parallel algorithms on the commutation class of a word ⋮ Algorithmic analysis of priority-based bin packing ⋮ Local consistency in parallel constraint satisfaction networks ⋮ An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs ⋮ An optimal EREW PRAM algorithm for minimum spanning tree verification ⋮ A polynomial algorithm for the extendability problem in bipartite graphs ⋮ An optimal parallel algorithm forc-vertex-ranking of trees ⋮ Fast parallel recognition of LR language suffixes ⋮ Load balancing for the parallel adaptive solution of partial differential equations ⋮ Fast parallel algorithm for polynomial interpolation ⋮ Approximating weighted matchings in parallel ⋮ A parallel algorithm for nearly optimal edge search ⋮ Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems ⋮ Improved parallel integer sorting without concurrent writing ⋮ Unified all-pairs shortest path algorithms in the chordal hierarchy ⋮ Sorting strings and constructing digital search trees in parallel ⋮ Parallel evaluation of arithmetic circuits ⋮ Parallel computation of polynomial GCD and some related parallel computations over abstract fields ⋮ Efficient massively parallel implementation of some combinatorial algorithms ⋮ Exploiting few inversions when sorting: Sequential and parallel algorithms ⋮ Simulating shared memory in real time: On the computation power of reconfigurable architectures ⋮ The interval-merging problem ⋮ \(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs ⋮ Transversal partitioning in balanced hypergraphs ⋮ Recognizing and representing proper interval graphs in parallel using merging and sorting ⋮ The complexity of parallel prefix problems on small domains ⋮ Separating the power of EREW and CREW PRAMs with small communication width ⋮ Efficient computation of implicit representations of sparse graphs ⋮ Straight-line programs in geometric elimination theory ⋮ On chromatic sums and distributed resource allocation ⋮ A canonical form of vector machines ⋮ The queue-read queue-write asynchronous PRAM model ⋮ The bulk-synchronous parallel random access machine ⋮ Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems ⋮ The complexity of the bootstraping percolation and other problems ⋮ An optimal parallel algorithm for digital curve segmentation ⋮ On the parallel complexity of loops ⋮ Planar stage graphs: Characterizations and applications ⋮ Adapting parallel algorithms to the W-stream model, with applications to graph problems ⋮ Oblivious algorithms for multicores and networks of processors ⋮ A time-optimal solution for the path cover problem on cographs. ⋮ List-ranking on interconnection networks. ⋮ On parallel recognition of cographs ⋮ Fast evaluation of interlace polynomials on graphs of bounded treewidth ⋮ Powers of geometric intersection graphs and dispersion algorithms ⋮ The saga of minimum spanning trees ⋮ Store-and-forward multicast routing on the mesh ⋮ Computational complexity of threshold automata networks under different updating schemes ⋮ On efficient implicit OBDD-based algorithms for maximal matchings ⋮ A parallel algorithm based on convexity for the computing of Delaunay tessellation ⋮ Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs ⋮ Parallel exact inference on the cell broadband engine processor ⋮ Unified parallel encoding and decoding algorithms for Dandelion-like codes ⋮ A linear time algorithm for finding all hinge vertices of a permutation graph ⋮ Reliable computations on faulty EREW PRAM ⋮ The element distinctness problem on one-tape Turing machines ⋮ An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs ⋮ Fast rehashing in PRAM emulations ⋮ An optimal parallel algorithm for the Euclidean distance maps of 2-D binary images ⋮ Optimal parallel algorithms for path problems on planar graphs ⋮ NC algorithms for the Single Most Vital Edge problem with respect to shortest paths ⋮ Efficient algorithms for shortest distance queries on special classes of polygons ⋮ Randomized multipacket routing and sorting on meshes ⋮ Fast randomized parallel methods for planar convex hull construction ⋮ Sequential and parallel algorithms for finding a maximum convex polygon ⋮ When is the multiaffine image of a cube a convex polygon? ⋮ The strong distance problem on the Cartesian product of graphs ⋮ Parallel algorithms for separable permutations ⋮ Efficiently parallelizable problems on a class of decomposable graphs ⋮ NFA reduction algorithms by means of regular inequalities ⋮ Constructing arrangements optimally in parallel ⋮ Improved parallel computations with Toeplitz-like and Hankel-like matrices ⋮ A spectral lower bound for the treewidth of a graph and its consequences ⋮ An optimal parallel algorithm for node ranking of cographs ⋮ Optimal parallel two dimensional text searching on a CREW PRAM ⋮ Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms ⋮ Boolean circuit programming: A new paradigm to design parallel algorithms ⋮ Simulating the CRCW PRAM on reconfigurable networks ⋮ Characterizing multiterminal flow networks and computing flows in networks of small treewidth ⋮ Computing Prüfer codes efficiently in parallel ⋮ An efficient parallel graph edge matching algorithm and its applications ⋮ Parallel construction and query of index data structures for pattern matching on square matrices ⋮ Algorithms for generalized vertex-rankings of partial k-trees ⋮ Algorithms for the parallel alternating direction access machine ⋮ An adjustable linear time parallel algorithm for maximum weight bipartite matching ⋮ Decompositions to degree-constrained subgraphs are simply reducible to edge-colorings ⋮ Parallel preprocessing for path queries without concurrent reading. ⋮ Computation of approximate polynomial GCDs and an extension ⋮ Reduction algorithms for graphs of small treewidth ⋮ Optimal gray-code labeling and recognition algorithms for hypercubes ⋮ A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs ⋮ A note on bitonic sorting ⋮ An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs ⋮ An optimal parallel algorithm for merging using multiselection
This page was built for publication:
