Sorting in \(c \log n\) parallel steps
From MaRDI portal
Publication:1056541
DOI10.1007/BF02579338zbMath0523.68048WikidataQ63431207 ScholiaQ63431207MaRDI QIDQ1056541
Endre Szemerédi, János Komlós, Miklós Ajtai
Publication date: 1983
Published in: Combinatorica (Search for Journal in Brave)
Related Items
A lower bound for sorting networks based on the shuffle permutation, LABELING POINTS WITH RECTANGLES OF VARIOUS SHAPES, OPTIMAL PARALLEL PREPROCESSING ALGORITHMS FOR TESTING WEAK VISIBILITY OF POLYGONS FROM SEGMENTS, Representing shared data on distributed-memory parallel computers, On the diameter and bisector size of Cayley graphs, Parallel matching for ranking all teams in a tournament, Searching games with errors -- fifty years of coping with liars, Deterministic Graphical Games Revisited, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, The generalized packet routing problem, Graphs whose every transitive orientation contains almost every relation, Improved sorting networks with O(log N) depth, Optimal merging and sorting on the EREW PRAM, A note on adaptive parallel sorting, Constructing sorting networks from k-sorters, Parametric search made practical, Negation-limited circuit complexity of symmetric functions, Optimal slope selection via expanders, Highly symmetric expanders, On O(Tlog T) reduction from RAM computations to satisfiability, A parallel-design distributed-implementation (PDDI) general-purpose computer, \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators, Finding Euler tours in parallel, On parallel integer sorting, Parallel comparison merging of many-ordered lists, Selecting distances in arrangements of hyperplanes spanned by points., Sorting roughly sorted sequences in parallel, Bounds on the size of test sets for sorting and related networks, A new scheme for the deterministic simulation of PRAMs in VLSI, A complexity theory of efficient parallel algorithms, Parallel selection, Partitioning arrangements of lines. I: An efficient deterministic algorithm, Construction of \(\epsilon\)-nets, Comment on Kochol's paper ``Efficient monotone circuits for threshold functions, The unpredictable deviousness of models, Improving the average delay of sorting, On the complexity of slice functions, More on the complexity of slice functions, On efficient parallel strong orientation, Distributed algorithms in synchronous broadcasting networks, Parallel ear decomposition search (EDS) and st-numbering in graphs, Distributed sorting algorithms for multi-channel broadcast networks, Towards optimal parallel bucket sorting, An optimal parallel algorithm for triangulating a set of points in the plane, An O(log n) time parallel algorithm for triangulating a set of points in the plane, An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits, A parallel bucket sort, Broadcasting with random faults, Eigenvalues and expanders, An efficient parallel algorithm for planarity, On the distribution of comparisons in sorting algorithms, Parallel computational geometry, L-infinity interdistance selection by parametric search, An efficient parallel algorithm for random sampling, Sorting in rounds, Optimal parallel selection has complexity O(log log N), Efficient monotone circuits for threshold functions, Hybridsort revisited and parallelized, The queue-read queue-write asynchronous PRAM model, Real-time emulations of bounded-degree networks, A note on the token distribution problem, Randomized optimal algorithm for slope selection, An optimal parallel adaptive sorting algorithm, Optimal randomized parallel algorithms for computational geometry, Finding effective ``Force targets for two-dimensional, multifinger frictional grips, An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model, A parallelization of Miller's \(n^{\log n}\) isomorphism technique, Parallel iterated bucket sort, Sorting in linear time?, More general parallel tree contraction: Register allocation and broadcasting in a tree, A simple optimal parallel algorithm for the minimum coloring problem on interval graphs, Shallow grates, Deterministic sorting in nearly logarithmic time on the hypercube and related computers, Iterated nearest neighbors and finding minimal polytopes, Computing the smallest \(k\)-enclosing circle and related problems, Algorithms for ham-sandwich cuts, On the relationship between the diameter and the size of a boundary of a directed graph, Methods for message routing in parallel machines, Multi-processor scheduling and expanders, A theory of strict P-completeness, Recursive construction for 3-regular expanders, Parallel integer sorting using small operations, A parallel algorithm for the generation of a permutation and applications, Better lower bounds for monotone threshold formulas, Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM, Braking the \(\Theta(n\log^ 2 n)\) barrier for sorting with faults, Sorting strings and constructing digital search trees in parallel, Exploiting few inversions when sorting: Sequential and parallel algorithms, Optimal slope selection via cuttings, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Periodic comparator networks, Comparator networks for binary heap construction, A note on constructing binary heaps with periodic networks., Parallel preprocessing for path queries without concurrent reading., Improved fast integer sorting in linear space, On the negation-limited circuit complexity of merging, Improving the efficiency of parallel minimum spanning tree algorithms, Algorithmic results for ordered median problems, Monotone simulations of non-monotone proofs., Monotone Boolean formulas can approximate monotone linear threshold functions, A unified \(O(\log N)\) and optimal sorting vector algorithm, Fast periodic correction networks, Dense expanders and pseudo-random bipartite graphs, A computer-assisted optimal depth lower bound for nine-input sorting networks, Fast algorithms for bit-serial routing on a hypercube, Single-exception sorting networks and the computational complexity of optimal sorting network verification, Expanders and Diffusers, Diameters and Eigenvalues
Cites Work
