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
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, Optimal parallel shortest paths in small treewidth digraphs, Shared memory simulations with triple-logarithmic delay, Fast deterministic simulation of computations on faulty parallel machines, An optimal parallel algorithm for digital curve segmentation using hough polygons and monotone function search, Parallel suffix sorting for large string analytics, An Improved Parallel Prefix Sums Algorithm, Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata, Time-optimal tree computations on sparse meshes, Deterministic parallel backtrack search, Two-variable linear programming in parallel, More Efficient Parallel Integer Sorting, On the complexity of generalized Q2R automaton, Parallel Triangular Mesh Refinement by Longest Edge Bisection, A faster parallel connectivity algorithm on cographs, Sorting and Permuting without Bank Conflicts on GPUs, Computing the L 1-diameter and center of a simple rectilinear polygon in parallel, Worst-case efficient external-memory priority queues, Solving fundamental problems on sparse-meshes, Efficient parallel computing with memory faults, 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, Parallel algorithm for minimum partial dominating set in unit disk graph, An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs, Simple Parallel Algorithms for Dynamic Range Products, An Efficient Algorithm for the 1D Total Visibility-Index Problem and Its Parallelization, An I/O Efficient Algorithm for Minimum Spanning Trees, A parallel naive approach for non-dominated sorting: a theoretical study considering PRAM CREW model, 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, Parallel lightweight wavelet tree, suffix array and FM-index construction, Parallel adaptive mesh refinement and redistribution on distributed memory computers, Maximum entropy and interval computations (September notes on summer impressions), A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, Efficient parallel graph algorithms for coarse grained multicomputers and BSP, A new algorithm for the integer knapsack problem and its parallelization, All Nearest Smallers Made Simple, A quadratic-time algorithm for smoothing interval functions, Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms, Parallel approximation schemes for problems on planar graphs, Efficiently Testing $$T$$-Interval Connectivity in Dynamic Graphs, Optimal parallel algorithms for proximate points, with applications, Parallel refinement and coarsening of tetrahedral meshes, Parallel Weighted Random Sampling, Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph, Practical Wavelet Tree Construction, Two parallel algorithms for finding all minimal maximum subsequences, Unnamed Item, Listing all spanning trees in Halin graphs — sequential and Parallel view, On the complexity of the stability problem of binary freezing totalistic cellular automata, The complexity of the asynchronous prediction of the majority automata, Nearly Work-Efficient Parallel Algorithm for Digraph Reachability, Efficient algorithmic learning of the structure of permutation groups by examples, An efficient parallel algorithm for shortest paths in planar layered digraphs, A practical algorithm for the minimum rectilinear Steiner tree, Adaptive and efficient mutual exclusion, Parallel volume meshing using face removals and hierarchical repartitioning, 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, Parallel algorithms on interval graphs, A simple optimal parallel algorithm for constructing a spanning tree of a trapezoid graph, Simple fast parallel hashing, Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching, On Synchronizing Tree Automata and Their Work–Optimal Parallel Run, Usable for Parallel Tree Pattern Matching, Efficient minimum spanning tree algorithms on the reconfigurable mesh, Data independence of read, write, and control structures in PRAM computations, Work-sensitive dynamic complexity of formal languages, On the strong distance problems of pyramid networks, Optimal shooting: Characterizations and applications, Parallel approximation for partial set cover, Two-variable linear programming in parallel, Computing parameters of sequence-based dynamic graphs, Very fast parallel algorithms for approximate edge coloring, Efficient parallel factorization and solution of structured and unstructured linear systems, Trade-offs between communication throughput and parallel time, The Hamiltonian problem on distance-hereditary graphs, 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, EFFICIENT SIMULATION OF AN ACYCLIC DIRECTED RECONFIGURABLE MODEL ON AN UNDIRECTED RECONFIGURABLE MODEL, A parallel hp‐FEM infrastructure for three‐dimensional structural acoustics, Unnamed Item, On Computable Numbers, Nonuniversality, and the Genuine Power of Parallelism, SIMULATING AN R-MESH ON AN LR-MESH IN CONSTANT TIME, Parallel algorithms for red--black trees, Hamiltonian paths in hypercubes with local traps, Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs, Priority queues on parallel machines, Parallel computation of the Burrows Wheeler transform in compact space, On the complexity of asynchronous freezing cellular automata, Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs, Additive tree 2-spanners of permutation graphs, Via Detours to I/O-Efficient Shortest Paths, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths, Unnamed Item, The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms, A new algorithm for computing orthogonal polynomials, Efficient parallel recognition of cographs, A Scalable Approach to Compute Delay Margin of a Class of Neutral-Type Time Delay Systems, 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, Very fast algorithms for implied barriers and moving-barrier options pricing, On the Strongly Connected and Biconnected Components of the Complement of Graphs, \#P-completeness of counting update digraphs, cacti, and series-parallel decomposition method, Space-efficient parallel merging, Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies, A fast parallel algorithm for minimum-cost small integral flows
