Applying Parallel Computation Algorithms in the Design of Serial Algorithms
From MaRDI portal
Publication:3763585
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
schedulingparallel algorithmsspanning treealgorithms on treesmax-flow-related problemsmin-ratio cycleparametric computation
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)
- 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
- OPTIMAL FACILITY LOCATION UNDER VARIOUS DISTANCE FUNCTIONS
- Can we compute the similarity between surfaces?
- Strongly polynomial-time approximation for a class of bicriteria problems.
- Optimal spanners for axis-aligned rectangles
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- Fractional 0-1 programming: applications and algorithms
- Efficient algorithms for the minimum diameter bridge problem
- Fast algorithms for diameter-optimally augmenting paths and trees
- Modifying edges of a network to obtain short subgraphs
- Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
- Almost optimal algorithms for diameter-optimally augmenting trees
- Bottleneck capacity expansion problems with general budget constraints
- Consecutive interval query and dynamic programming on intervals
- Packing two disks into a polygonal environment.
- On the complexity and approximability of budget-constrained minimum cost flows
- Selecting distances in the plane
- A strongly polynomial algorithm for line search in submodular polyhedra
- A sweepline algorithm to solve the two-center problem
- Optimal Movement of Mobile Sensors for Barrier Coverage of a Planar Region
- Computing all large sums-of-pairs in \(\mathbb R^n\) and the discrete planar two-watchtower problem
- Placing two disks in a convex polygon
- On finding widest empty curved corridors
- Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\)
- The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
- Constructive Interference in Parallel Algorithms
- Minmax regret \(k\)-sink location on a dynamic path network with uniform capacities
- Improved algorithms for some competitive location centroid problems on paths, trees and graphs
- An adaptive and cost-optimal parallel algorithm for minimum spanning trees
- Partitioning point sets in arbitrary dimension
- Title not available (Why is that?)
- An inverse model for the most uniform problem
- Simplex Range Searching and Its Variants: A Review
- Obnoxious facility location: complete service with minimal harm
- An incremental and parametrical algorithm for convex-concave fractional programming with a single constraint
- Combinatorially implosive algorithms
- On some geometric selection and optimization problems via sorted matrices
- Covering a set of line segments with a few squares
- Using sparsification for parametric minimum spanning tree problems
- ON ENUMERATING AND SELECTING DISTANCES
- Solving NP-hard problems in 'almost trees': vertex cover
- Efficient algorithms for determining 3D biplane imaging geometry
- Parallel and sequential computation: A statistician's view
- Tow algorithms for finding a minimal ratio hamiltonian cycle in a network
- Diameter, width, closest line pair, and parametric searching
- 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
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)
