Slowing down sorting networks to obtain faster sorting algorithms

From MaRDI portal
Publication:4601942

DOI10.1145/7531.7537zbMath1378.68037OpenAlexW2013382394WikidataQ127516402 ScholiaQ127516402MaRDI QIDQ4601942

Richard John Cole

Publication date: 25 January 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/7531.7537



Related Items

Discrete Fréchet distance for closed curves, Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows, Dispersing facilities on planar segment and circle amidst repulsion, Efficient \(k\)-center algorithms for planar points in convex position, The \(k\)-centrum multi-facility location problem, Guarding a terrain by two watchtowers, Covering convex polygons by two congruent disks, Intersecting disks using two congruent disks, Intersecting disks using two congruent disks, Covering uncertain points in a tree, Optimal Movement of Mobile Sensors for Barrier Coverage of a Planar Region, An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees, Covering convex polygons by two congruent disks, Optimal Algorithms for Geometric Centers and Depth, Iterated nearest neighbors and finding minimal polytopes, Computing the similarity between moving curves, Computing the smallest \(k\)-enclosing circle and related problems, Extremal polygon containment problems, Improved algorithms for the bichromatic two-center problem for pairs of points, Selecting distances in the plane, Reverse shortest path problem for unit-disk graphs, An approximation algorithm for least median of squares regression, Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications, Computing a centerpoint of a finite planar set of points in linear time, Partitioning point sets in arbitrary dimension, Efficient algorithms for center problems in cactus networks, Matroid and knapsack center problems, Computing the Center of Uncertain Points on Tree Networks, Approximating points by a piecewise linear function, Using sparsification for parametric minimum spanning tree problems, Parametric problems on graphs of bounded tree-width, Optimal parametric search on graphs of bounded tree-width, The (1|1)-Centroid Problem in the Plane with Distance Constraints, Rearranging a sequence of points onto a line, On the planar piecewise quadratic 1-center problem, LOCATING AN OBNOXIOUS LINE AMONG PLANAR OBJECTS, Computing the smallest k-enclosing circle and related problems, Can we compute the similarity between surfaces?, Distance-constrained multifacility minimax location problems on tree networks, LABELING POINTS WITH RECTANGLES OF VARIOUS SHAPES, Efficient piecewise-linear function approximation using the uniform metric, L-infinity interdistance selection by parametric search, An efficient algorithm for the proximity connected two center problem, Parametric search made practical, Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain, Selecting distances in arrangements of hyperplanes spanned by points., Revisiting \(k\)-sum optimization, Computing the Fréchet distance between piecewise smooth curves, The multi-service center problem, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Fréchet distance with speed limits, Constant work-space algorithms for facility location problems, Geometric p-Center Problems with Centers Constrained to Two Lines, New Upper Bounds on Continuous Tree Edge-Partition Problem, The two-center problem of uncertain points on a real line, Some variations on constrained minimum enclosing circle problem, Improved algorithms for several network location problems with equality measures., Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\), Link distance and shortest path problems in the plane, Backup 2-center on interval graphs, Parallel selection, Partitioning arrangements of lines. I: An efficient deterministic algorithm, Construction of \(\epsilon\)-nets, The complexity of hyperplane depth in the plane, A note on searching line arrangements and applications, Exact algorithms for the bottleneck Steiner tree problem, An inverse model for the most uniform problem, Shortest path problems on a polyhedral surface, Computing the Fréchet distance between simple polygons, A generalized model of equality measures in network location problems, Efficient planar two-center algorithms, One-dimensional \(k\)-center on uncertain data, Finding effective ``Force targets for two-dimensional, multifinger frictional grips, Efficient algorithms for the one-dimensional \(k\)-center problem, Geometric pattern matching under Euclidean motion, A generalized approximation framework for fractional network flow and packing problems, Diameter, width, closest line pair, and parametric searching, Approximate parametric searching, Optimal slope selection via expanders, Computing the center of uncertain points on tree networks, Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\)., Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches, Strongly polynomial-time approximation for a class of bicriteria problems., Parametric search: three new applications, Efficient algorithms for the sum selection problem and \(k\) maximum sums problem, The constrained minimum weighted sum of job completion times problem, Computing the center region and its variants, ON ENUMERATING AND SELECTING DISTANCES, Linear-Time Fitting of a k-Step Function, A note on computing the center of uncertain data on the real line, Center location problems on tree graphs with subtree-shaped customers, Unnamed Item, Efficient parallel algorithms for r-dominating set and p-center problems on trees, Computing and minimizing the relative regret in combinatorial optimization with interval data, Output-sensitive results on convex hulls, extreme points, and related problems, Dynamic ham-sandwich cuts in the plane, A selectable sloppy heap, Improved complexity results for several multifacility location problems on trees, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Continuous bottleneck tree partitioning problems, Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time, New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems, Optimal movement of mobile sensors for barrier coverage of a planar region, A combinatorial algorithm for the ordered 1-median problem on cactus graphs, Computing a geodesic two-center of points in a simple polygon, One-way and round-trip center location problems, An O(n log n)-Time Algorithm for the k-Center Problem in Trees, Locating two obnoxious facilities using the weighted maximin criterion, OPTIMAL FACILITY LOCATION UNDER VARIOUS DISTANCE FUNCTIONS, On the planar two-center problem and circular hulls, Locating service centers with precedence constraints, The centdian subtree on tree networks, Algorithmic results for ordered median problems, Optimal point movement for covering circular regions