Applying Parallel Computation Algorithms in the Design of Serial Algorithms

DOI10.1145/2157.322410zbMath0627.68034OpenAlexW2097004206WikidataQ59700079 ScholiaQ59700079MaRDI QIDQ3763585

Publication date: 1983

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

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.90.741

zbMATH Keywords

scheduling parallel algorithms spanning tree algorithms on trees max-flow-related problems min-ratio cycle parametric computation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Theory of operating systems (68N25) Algorithms in computer science (68W99)

Related Items

Building bridges between convex regions, Packing two disks in a polygon, Iterated nearest neighbors and finding minimal polytopes, Computing the similarity between moving curves, The geodesic 2-center problem in a simple polygon, Computing the smallest \(k\)-enclosing circle and related problems, Computing maximum mean cuts, Extremal polygon containment problems, Improved algorithms for the bichromatic two-center problem for pairs of points, Budget-constrained minimum cost flows, 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, Partitioning point sets in arbitrary dimension, The economic lot-sizing problem with an emission capacity constraint, On minimum and maximum spanning trees of linearly moving points, Optimal edge ranking of trees in polynomial time, Can we compute the similarity between surfaces?, A linear time randomizing algorithm for searching ranked functions, Orthogonal queries in segments, The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time, Efficient piecewise-linear function approximation using the uniform metric, On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree, L-infinity interdistance selection by parametric search, The maximin line problem with regional demand, Point location in zones of \(k\)-flats in arrangements, A deterministic algorithm for the three-dimensional diameter 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., Packing two disks into a polygonal environment., Fast algorithms for collision and proximity problems involving moving geometric objects, Revisiting \(k\)-sum optimization, Fractional 0-1 programming: applications and algorithms, Queries on Voronoi diagrams on moving points, Computing the Fréchet distance between piecewise smooth curves, Optimal slope selection via cuttings, The inverse-parametric knapsack problem, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Compact location problems, Consecutive interval query and dynamic programming on intervals, Fréchet distance with speed limits, Decomposable multi-parameter matroid optimization problems., Farthest-polygon Voronoi diagrams, Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\), Continuous location of dimensional structures., Parallel selection, Weight reduction problems with certain bottleneck objectives., Partitioning arrangements of lines. I: An efficient deterministic algorithm, Construction of \(\epsilon\)-nets, Exact algorithms for the bottleneck Steiner tree problem, An inverse model for the most uniform problem, Prune-and-search with limited workspace, Computing the Fréchet distance between simple polygons, Randomized optimal algorithm for slope selection, One-dimensional \(k\)-center on uncertain data, Finding effective ``Force targets for two-dimensional, multifinger frictional grips, On enclosing k points by a circle, Off-line dynamic maintenance of the width of a planar point set, Geometric pattern matching under Euclidean motion, Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points, A generalized approximation framework for fractional network flow and packing problems, Diameter, width, closest line pair, and parametric searching, On ray shooting in convex polytopes, Approximate parametric searching, Optimal slope selection via expanders, Maximum mean weight cycle in a digraph and minimizing cycle time of a logic chip, 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., Optimal spanners for axis-aligned rectangles, Optimization with additional variables and constraints, Computing the geodesic center of a simple polygon, Submodular function minimization, Center location problems on tree graphs with subtree-shaped customers, A fast algorithm for the alpha-connected two-center decision problem, The cyclical scheduling problem, On some geometric selection and optimization problems via sorted matrices, Computing and minimizing the relative regret in combinatorial optimization with interval data, A near-linear algorithm for the planar segment-center problem, Efficient randomized algorithms for some geometric optimization problems, Output-sensitive results on convex hulls, extreme points, and related problems, Single facility collection depots location problem in the plane, Dynamic ham-sandwich cuts in the plane, Modifying edges of a network to obtain short subgraphs, Computing all large sums-of-pairs in \(\mathbb R^n\) and the discrete planar two-watchtower problem, 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, Placing two disks in a convex polygon, Acrophobic guard watchtower problem, On the decisional complexity of problems over the reals, An adaptive and cost-optimal parallel algorithm for minimum spanning trees, Solving NP-hard problems in 'almost trees': vertex cover, Algorithms and complexity analysis for some flow problems, A sweepline algorithm to solve the two-center problem, An incremental and parametrical algorithm for convex-concave fractional programming with a single constraint, Algorithmic results for ordered median problems, Efficient algorithms for determining 3D biplane imaging geometry, Efficient algorithms for the minimum diameter bridge problem, Approximation algorithms for the min-max mixed rural postmen cover problem and its variants, Faster algorithms for largest empty rectangles and boxes, On the complexity and approximability of budget-constrained minimum cost flows, Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts, Selecting distances in the plane, Efficient algorithms for center problems in cactus networks, The Parametric Closure Problem, Approximating points by a piecewise linear function, Improved algorithms for some competitive location centroid problems on paths, trees and graphs, The constrained minimum spanning tree problem, Using sparsification for parametric minimum spanning tree problems, Constrained square-center problems, Space-sweep algorithms for parametric optimization, Parametric problems on graphs of bounded tree-width, Selection in monotone matrices and computing k th nearest neighbors, Optimal parametric search on graphs of bounded tree-width, The (1|1)-Centroid Problem in the Plane with Distance Constraints, Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, On the planar piecewise quadratic 1-center problem, LOCATING AN OBNOXIOUS LINE AMONG PLANAR OBJECTS, Computing the smallest k-enclosing circle and related problems, Repetitive hidden-surface-removal for polyhedral scenes, Optimal Embedding into Star Metrics, Constructing the minimization diagram of a two-parameter problem, Distance-constrained multifacility minimax location problems on tree networks, On finding widest empty curved corridors, LABELING POINTS WITH RECTANGLES OF VARIOUS SHAPES, CYLINDRICAL HIERARCHY FOR DEFORMING NECKLACES, Almost optimal algorithms for diameter-optimally augmenting trees, An efficient algorithm for the proximity connected two center problem, A general approximation method for bicriteria minimization problems, Linear-time fitting of a \(k\)-step function, Computing constrained minimum-width annuli of point sets, Generalized max flows and augmenting paths, Integrality in the multinetwork min‐cost equal‐flow problem, The quickest flow problem, The multi-weighted spanning tree problem, On reverse shortest paths in geometric proximity graphs, Geometric pattern matching in d-dimensional space, Dispersing facilities on planar segment and circle amidst repulsion, Geometric p-Center Problems with Centers Constrained to Two Lines, A strongly polynomial algorithm for line search in submodular polyhedra, New Upper Bounds on Continuous Tree Edge-Partition Problem, The two-center problem of uncertain points on a real line, Simplex Range Searching and Its Variants: A Review, Three problems about simple polygons, Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover, Tow algorithms for finding a minimal ratio hamiltonian cycle in a network, Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection, OBNOXIOUS FACILITY LOCATION: COMPLETE SERVICE WITH MINIMAL HARM, Linear approximation of simple objects, A note on searching line arrangements and applications, Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees, A generalized model of equality measures in network location problems, Efficient planar two-center algorithms, Bisecting three classes of lines, When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation, A submodular optimization problem with side constraints, Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks, Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D, Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\)., The \(k\)-centrum multi-facility location problem, Fitting rectilinear polgonal curves to a set of points in the plane., An efficient algorithm for the three-dimensional diameter problem, Bottleneck Capacity Expansion Problems with General Budget Constraints, SMOOTHING IMPRECISE 1.5D TERRAINS, Parametric search: three new applications, Sigma-local graphs, Efficient algorithms for the sum selection problem and \(k\) maximum sums problem, Computing the center region and its variants, Simple algorithms for partial point set pattern matching under rigid motion, ON ENUMERATING AND SELECTING DISTANCES, An improved algorithm for diameter-optimally augmenting paths in a metric space, A linear-time algorithm for solving continuous maximin knapsack problems, Unnamed Item, On some geometric selection and optimization problems via sorted matrices, Algorithms for covering multiple barriers, Linear-Time Fitting of a k-Step Function, Guarding a terrain by two watchtowers, Intersecting disks using two congruent disks, An FPTAS for the knapsack problem with parametric weights, A new contraction technique with applications to congruency-constrained cuts, Intersecting disks using two congruent disks, Minimizing the Maximum Moving Cost of Interval Coverage, A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives, COVERING A POINT SET BY TWO DISJOINT RECTANGLES, EFFICIENT ALGORITHMS FOR THE OPTIMAL-RATIO REGION DETECTION PROBLEMS IN DISCRETE GEOMETRY WITH APPLICATIONS, Traffic Networks and Flows over Time, Minimizing Distance-to-Sight in Polygonal Domains, Covering a set of line segments with a few squares, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Minmax regret \(k\)-sink location on a dynamic path network with uniform capacities, A combinatorial algorithm for the ordered 1-median problem on cactus graphs, Assigning weights to minimize the covering radius in the plane, One-way and round-trip center location problems, Optimal Movement of Mobile Sensors for Barrier Coverage of a Planar Region, Locating two obnoxious facilities using the weighted maximin criterion, Optimal Algorithms for Geometric Centers and Depth, OPTIMAL FACILITY LOCATION UNDER VARIOUS DISTANCE FUNCTIONS, On the planar two-center problem and circular hulls, Optimal point movement for covering circular regions