Publication:4023519
From MaRDI portal
zbMath0781.68009MaRDI QIDQ4023519
Publication date: 23 January 1993
68Q25: Analysis of algorithms and problem complexity
68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68W15: Distributed algorithms
Related Items
Parallel algorithms on interval graphs, Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs, EFFICIENT SIMULATION OF AN ACYCLIC DIRECTED RECONFIGURABLE MODEL ON AN UNDIRECTED RECONFIGURABLE MODEL, Unnamed Item, A COST-OPTIMAL EREW BREADTH-FIRST ALGORITHM FOR ORDERED TREES, WITH APPLICATIONS∗, MODELS AND RESOURCE METRICS FOR PARALLEL AND DISTRIBUTED COMPUTATION∗, FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH, An efficient parallel algorithm for shortest paths in planar layered digraphs, A parallel hp‐FEM infrastructure for three‐dimensional structural acoustics, DESIGNING PARALLEL ALGORITHMS FOR HIERARCHICAL SMP CLUSTERS, A GENERAL PRAM SIMULATION SCHEME FOR CLUSTERED MACHINES, TIME AND ENERGY OPTIMAL LIST RANKING ALGORITHMS ON THE k-CHANNEL BROADCAST COMMUNICATION MODEL WITH NO COLLISION DETECTION, Very fast parallel algorithms for approximate edge coloring, Trade-offs between communication throughput and parallel time, Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries, Parallel output-sensitive algorithms for combinatorial and linear algebra problems, Parallel algorithms for red--black trees, Deterministic parallel backtrack search, Two-variable linear programming in parallel, A simple optimal parallel algorithm for constructing a spanning tree of a trapezoid graph, SIMULATING AN R-MESH ON AN LR-MESH IN CONSTANT TIME, The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms, 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?, NFA reduction algorithms by means of regular inequalities, The interval-merging problem, \(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs, Recognizing and representing proper interval graphs in parallel using merging and sorting, Store-and-forward multicast routing on the mesh, The queue-read queue-write asynchronous PRAM model, The bulk-synchronous parallel random access machine, Improved parallel computations with Toeplitz-like and Hankel-like matrices, 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, Simulating the CRCW PRAM on reconfigurable networks, Characterizing multiterminal flow networks and computing flows in networks of small treewidth, An efficient parallel graph edge matching algorithm and its applications, Parallel construction and query of index data structures for pattern matching on square matrices, Decompositions to degree-constrained subgraphs are simply reducible to edge-colorings, A note on bitonic sorting, An optimal parallel algorithm for merging using multiselection, \(O(\log n)\) numerical algorithms on a mesh with wormhole routing, An efficient parallel algorithm for the single function coarsest partition problem, Local consistency in parallel constraint satisfaction networks, Load balancing for the parallel adaptive solution of partial differential equations, Fast parallel algorithm for polynomial interpolation, 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, Transversal partitioning in balanced hypergraphs, 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, Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems, An optimal parallel algorithm for digital curve segmentation, On the parallel complexity of loops, Planar stage graphs: Characterizations and applications, A time-optimal solution for the path cover problem on cographs., List-ranking on interconnection networks., Powers of geometric intersection graphs and dispersion algorithms, Computing Prüfer codes efficiently in parallel, Algorithms for generalized vertex-rankings of partial k-trees, Algorithms for the parallel alternating direction access machine, Optimal gray-code labeling and recognition algorithms for hypercubes, An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs, Coloring permutation graphs in parallel, Parallel algorithms for separable permutations, Efficiently parallelizable problems on a class of decomposable graphs, Constructing arrangements optimally in parallel, Parallel preprocessing for path queries without concurrent reading., Computation of approximate polynomial GCDs and an extension, Reduction algorithms for graphs of small treewidth, A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs, Fringe analysis of synchronized parallel insertion algorithms in 2--3 trees., Two optimal parallel algorithms on the commutation class of a word, Parallel adaptive mesh refinement and redistribution on distributed memory computers, Maximum entropy and interval computations (September notes on summer impressions), A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, A new algorithm for the integer knapsack problem and its parallelization, A quadratic-time algorithm for smoothing interval functions, Parallel approximation schemes for problems on planar graphs, Efficient algorithmic learning of the structure of permutation groups by examples, A practical algorithm for the minimum rectilinear Steiner tree, Parallel volume meshing using face removals and hierarchical repartitioning, Efficient minimum spanning tree algorithms on the reconfigurable mesh, Data independence of read, write, and control structures in PRAM computations, A faster parallel connectivity algorithm on cographs, On coding labeled trees, On the parallel computation of the biconnected and strongly connected co-components of graphs, Construction of universal one-way hash functions: tree hashing revisited, On the strong distance problems of pyramid networks, Efficient parallel factorization and solution of structured and unstructured linear systems, The Hamiltonian problem on distance-hereditary graphs, A new algorithm for computing orthogonal polynomials, Efficient parallel recognition of cographs, Checking if there exist a monotonic function that is consistent with the measurements: an efficient algorithm, Efficient parallel algorithm to compute a doubly perfect elimination ordering of a doubly chordal graph, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, Space-efficient parallel merging, On the Strongly Connected and Biconnected Components of the Complement of Graphs
