scientific article; zbMATH DE number 1142306
From MaRDI portal
Publication:4385522
zbMath0900.68267MaRDI QIDQ4385522
Vijaya Ramachandran, Richard M. Karp
Publication date: 4 May 1998
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16)
Related Items
Oracle computations in parallel numerical linear algebra, Improved parallel solution of a triangular linear system, On the computation of pfaffians, The parallel solution of domination problems on chordal and strongly chordal graphs, Complexity models for incremental computation, Dynamic scheduling on parallel machines, Locality-preserving hash functions for general purpose parallel computation, Nearly-perfect hypergraph packing is in NC, An insight on PRAM computational bounds, A theory of strict P-completeness, An optimal EREW PRAM algorithm for minimum spanning tree verification, A parallel list update problem, A note on parallel complexity of maximum \(f\)-matching, Parallel approximation algorithms for maximum weighted matching in general graphs, A new thesis concerning synchronised parallel computing -- simplified parallel ASM thesis, More agents may decrease global work: a case in butterfly decontamination, The interval-merging problem, The queue-read queue-write asynchronous PRAM model, The bulk-synchronous parallel random access machine, ERCW PRAMs and optical communication, Optimal algorithms of Gram-Schmidt type, A bridging model for multi-core computing, On parallel recognition of cographs, Parallel tree pattern matching, A complexity theory of efficient parallel algorithms, Integer merging on EREW PRAM, Parallel recognition of complement reducible graphs and cotree construction, Lower bounds on the computational power of an optical model of computation, Fast rectangular matrix multiplication and some applications, A unified approach to parallel depth-first traversals of general trees, Circuits for computing the GCD of two polynomials over an algebraic number field, On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields, Matrix inversion in RNC\(^ 1\), Achieving optimal CRCW PRAM fault-tolerance, A note on the subtree isomorphism for ordered trees and related problems, Las Vegas RNC algorithms for unary weighted perfect matching and \(T\)-join problems, Data-movement-intensive problems: Two folk theorems in parallel computation revisited, Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem, On the evaluation of the eigenvalues of a banded Toeplitz block matrix, Maintaining bridge-connected and biconnected components on-line, Reliable computations on faulty EREW PRAM, Learning in parallel, A model classifying algorithms as inherently sequential with applications to graph searching, Fast rehashing in PRAM emulations, Parallel algorithms for priority queue operations, Optimal parallel execution of complete binary trees and grids into most popular interconnection networks, A simple randomized parallel algorithm for maximal f-matchings, On 2-QBF truth testing in parallel, The maximal \(f\)-dependent set problem for planar graphs is in NC, Optimal parallel algorithms for path problems on planar graphs, Multilist layering: Complexity and applications, Efficient parallel recognition of some circular arc graphs. II, Efficient parallel algorithms for computing all pair shortest paths in directed graphs, Parallel solution of Toeplitzlike linear systems, The complexity of circuit value and network stability, An efficient algorithm for the Knight's tour problem, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, A new graph triconnectivity algorithm and its parallelization, Multiplication, division, and shift instructions in parallel random access machines, A parallel algorithm for minimum weighted colouring of triangulated graphs, Efficient parallel algorithms for shortest paths in planar digraphs, PRAMs with variable word-size, An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3, Approximating the minimum-cost maximum flow is P-complete, Matching theory -- a sampler: From Dénes König to the present, Testing a simple polygon for monotonicity optimally in parallel, Efficient parallel term matching and anti-unification, Deciding bisimilarity is P-complete, Two \(P\)-complete problems in the theory of the reals, Parallel search algorithms for graphs and trees, Polynomial division with a remainder by means of evaluation and interpolation, An optimal parallel algorithm for computing furthest neighbors in a tree, Parametrization of Newton's iteration for computations with structured matrices and applications, I/O- and CPU-optimal recognition of strongly connected components, Improved processor bounds for parallel algorithms for weighted directed graphs, Parallel heap: an optimal parallel priority queue, A randomized sublinear time parallel GCD algorithm for the EREW PRAM, Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs, Parallel merging with restriction, Improved parallel computations with Toeplitz-like and Hankel-like matrices, Product rules for the displacement of near-Toeplitz matrices, An efficient parallel algorithm for finding minimum weight matching for points on a convex polygon, A parallel extended GCD algorithm, Parallel processing for difficult combinatorial optimization problems, A nearly parallel algorithm for the Voronoi diagram of a convex polygon, Fast rectangular matrix multiplication and applications, On parallel methods for boundary value ODEs, A fast parallel algorithm for finding Hamiltonian cycles in dense graphs, The parallel complexity of approximating the high degree subgraph problem, Optical computing, Scheduling inverse trees under the communication model of the LogP-machine, Synthesizers and their application to the parallel construction of pseudo-random functions, Parallel construction and query of index data structures for pattern matching on square matrices, Topological queries in spatial databases, A parallel algorithm for constructing projection polyhedra, Fast parallel constraint satisfaction, Improved algorithms for graph four-connectivity, The parallel complexity of two problems on concurrency, The complexity of computing maximal word functions, Probabilistic methods in coloring and decomposition problems, NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems, The maximal f-dependent set problem for planar graphs is in NC, Parallel NC-algorithms for multifacility location problems with mutual communication and their applications, Optimal parallel verification of minimum spanning trees in logarithmic time, Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs, Summing up function values in parallel: A complexity analysis, Sieve algorithms for perfect power testing, Finding least-weight subsequences with fewer processors, Fast parallel constraint satisfaction, On parallelizing a greedy heuristic for finding small dominant sets, Logic programs and connectionist networks, On the parallel complexity of digraph reachability, Gossiping and broadcasting versus computing functions in networks, A faster parallel connectivity algorithm on cographs, Finding the k shortest paths in parallel, An optimal parallel algorithm for maximal matching, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Planarity testing in parallel, Pipelined Decomposable BSP Computers, Random parallel algorithms for finding exact branchings, perfect matchings, and cycles, On self-stabilizing wait-free clock synchronization, Dynamic expression trees, Efficient parallel computing with memory faults, Efficient parallel algorithms for shortest paths in planar graphs, Parallel algorithms for all minimum link paths and link center problems, A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity, Parallel maximum independent set in convex bipartite graphs, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, A fast and efficient NC algorithm for maximal matching, Improved parallel depth-first search in undirected planar graphs, Optimal parallel algorithms for rectilinear link-distance problems, An efficient parallel algorithm for shortest paths in planar layered digraphs, A time-optimal parallel algorithm for three-dimensional convex hulls, Finding a closet visible vertex pair between two polygons, Parallel algorithms for the domination problems in trapezoid graphs, Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM, An optimal parallel algorithm for planar cycle separators, An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs, MIMD VERSUS SIMD COMPUTATION: EXPERIENCE WITH NON-NUMERIC PARALLEL ALGORITHMS∗ †, The parallel complexity of growth models, On randomized versus deterministic computation, 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, Designing checkers for programs that run in parallel, The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem, A remark on maximum matching of line graphs, Graph Connectivity in Log Steps Using Label Propagation, Optimal and nearly optimal algorithms for approximating polynomial zeros, Parallel complexity of partitioning a planar graph into vertex-induced forests, A canonical form of vector machines, Parallel approximation schemes for problems on planar graphs, Graph layout problems, On languages accepted with simultaneous complexity bounds and their ranking problem, On parallel complexity of maximum f-matching and the degree sequence problem, Parallel algorithms for certain matrix computations, On the computational power of self-stabilizing systems, Parallel algorithms for the minimum cut and the minimum length tree layout problems, Queries with arithmetical constraints, Planar stage graphs: Characterizations and applications, Fast deterministic simulation of computations on faulty parallel machines, A time-optimal solution for the path cover problem on cographs., Algorithms for testing occurrences of length 4 patterns in permutations, Parallelizing time with polynomial circuits, Graph coloring on coarse grained multicomputers, The computational complexity of generating random fractals, Representing shared data on distributed-memory parallel computers, A modular reduction for GCD computation., Nearly Work-Efficient Parallel Algorithm for Digraph Reachability, Optimal computation of shortest paths on doubly convex bipartite graphs, Gossiping and broadcasting versus computing functions in networks., A Characterisation of NL Using Membrane Systems without Charges and Dissolution, On the computational complexity of coalitional resource games, An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals, Data independence of read, write, and control structures in PRAM computations, The Hamilton circuit problem on grids, Cook's versus Valiant's hypothesis, Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms, Computing with Spikes: The Advantage of Fine-Grained Timing, Unnamed Item, Parallel algorithms for priority queue operations, Efficiently parallelizable problems on a class of decomposable graphs, The Hamiltonian problem on distance-hereditary graphs, An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects, Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search, More Efficient Parallel Integer Sorting, Constructing arrangements optimally in parallel, Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set, Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Computing Prüfer codes efficiently in parallel, Some Related Functions to Integer GCD and Coprimality, A selected tour of the theory of identification matrices, Algorithms for the parallel alternating direction access machine, Improved algorithms via approximations of probability distributions, An algorithm for the Tutte polynomials of graphs of bounded treewidth, String distances and intrusion detection: Bridging the gap between formal languages and computer security, On designing optimal parallel triangular solvers., Approximating unweighted connectivity problems in parallel, Homomorphic Encryption, Space-efficient parallel merging
