Applying Parallel Computation Algorithms in the Design of Serial Algorithms

DOI10.1145/2157.322410zbMATH Open0627.68034DBLPjournals/jacm/Megiddo83OpenAlexW2097004206WikidataQ59700079 ScholiaQ59700079MaRDI QIDQ3763585FDOQ3763585

Authors: Nimrod Megiddo 

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

Recommendations

• scientific article; zbMATH DE number 53193
• Publication:4864234
• scientific article; zbMATH DE number 107950
• scientific article; zbMATH DE number 4037239
• scientific article; zbMATH DE number 3889284

zbMATH Keywords

schedulingparallel algorithmsspanning treealgorithms on treesmax-flow-related problemsmin-ratio cycleparametric computation

Mathematics Subject Classification ID

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

Cited In (only showing first 100 items - show all)

• Locating two obnoxious facilities using the weighted maximin criterion
• Constructing the minimization diagram of a two-parameter problem
• The inverse-parametric knapsack problem
• New Upper Bounds on Continuous Tree Edge-Partition Problem
• SMOOTHING IMPRECISE 1.5D TERRAINS
• Submodular function minimization
• Layouts for improved hierarchical parallel computations
• On ray shooting in convex polytopes
• A linear-time algorithm for solving continuous maximin knapsack problems
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• PRO: a model for the design and analysis of efficient and scalable parallel algorithms
• Farthest-polygon Voronoi diagrams
• Selecting distances in arrangements of hyperplanes spanned by points.
• Slowing down sorting networks to obtain faster sorting algorithms
• Extremal polygon containment problems
• Computing the Fréchet distance between simple polygons
• Budget-constrained minimum cost flows
• Computing the smallest \(k\)-enclosing circle and related problems
• LABELING POINTS WITH RECTANGLES OF VARIOUS SHAPES
• Approximating points by a piecewise linear function
• A note on searching line arrangements and applications
• Efficient randomized algorithms for some geometric optimization problems
• Constrained square-center problems
• An approximation algorithm for least median of squares regression
• On enclosing k points by a circle
• Single facility collection depots location problem in the plane
• Center location problems on tree graphs with subtree-shaped customers
• Continuous bottleneck tree partitioning problems
• The economic lot-sizing problem with an emission capacity constraint
• Distance-constrained multifacility minimax location problems on tree networks
• Approximate parametric searching
• Parallel selection
• The cyclical scheduling problem
• The maximin line problem with regional demand
• Output-sensitive results on convex hulls, extreme points, and related problems
• Randomized optimal algorithm for slope selection
• A linear time randomizing algorithm for searching ranked functions
• Linear-time fitting of a \(k\)-step function
• Linear-time fitting of a \(k\)-step function
• L-infinity interdistance selection by parametric search
• Geometric pattern matching under Euclidean motion
• The geodesic 2-center problem in a simple polygon
• On some geometric selection and optimization problems via sorted matrices
• Iterated nearest neighbors and finding minimal polytopes
• The \(k\)-centrum multi-facility location problem
• Continuous location of dimensional structures.
• Three problems about simple polygons
• Parametric problems on graphs of bounded tree-width
• Prune-and-search with limited workspace
• Efficient algorithms for center problems in cactus networks
• Covering a point set by two disjoint rectangles
• A near-linear algorithm for the planar segment-center problem
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
• One-way and round-trip center location problems
• Weight reduction problems with certain bottleneck objectives.
• Optimal edge ranking of trees in polynomial time
• Compact location problems
• Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
• Fréchet distance with speed limits
• Construction of \(\epsilon\)-nets
• Computing the Fréchet distance between piecewise smooth curves
• The \((1 | 1)\)-centroid problem in the plane with distance constraints
• Algorithmic results for ordered median problems
• Computing and minimizing the relative regret in combinatorial optimization with interval data
• On the planar piecewise quadratic 1-center problem
• One-dimensional \(k\)-center on uncertain data
• Exact algorithms for the bottleneck Steiner tree problem
• New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems
• Fast algorithms for collision and proximity problems involving moving geometric objects
• A generalized model of equality measures in network location problems
• Parametric search made practical
• Optimal slope selection via expanders
• Simple algorithms for partial point set pattern matching under rigid motion
• Queries on Voronoi diagrams on moving points
• Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications
• Computing the geodesic center of a simple polygon
• Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\).
• Revisiting \(k\)-sum optimization
• On the planar two-center problem and circular hulls
• Efficient piecewise-linear function approximation using the uniform metric
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• Computing maximum mean cuts
• Optimal movement of mobile sensors for barrier coverage of a planar region
• A fast algorithm for the alpha-connected two-center decision problem
• Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points
• The constrained minimum spanning tree problem
• Fitting rectilinear polgonal curves to a set of points in the plane.
• The quickest flow problem
• Optimal slope selection via cuttings
• Improved algorithms for the bichromatic two-center problem for pairs of points
• A generalized approximation framework for fractional network flow and packing problems
• Title not available (Why is that?)
• Reverse shortest path problem for unit-disk graphs
• Geometric pattern matching in d-dimensional space
• Packing two disks in a polygon
• Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches
• Maximum mean weight cycle in a digraph and minimizing cycle time of a logic chip
• Dynamic ham-sandwich cuts in the plane
• Off-line dynamic maintenance of the width of a planar point set
• Finding effective ``Force targets for two-dimensional, multifinger frictional grips

This page was built for publication: Applying Parallel Computation Algorithms in the Design of Serial Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3763585)