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
- Parametric search: three new applications
- A submodular optimization problem with side constraints
- Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection
- Linear approximation of simple objects
- Faster algorithms for next breakpoint and max value for parametric global minimum cuts
- Efficient planar two-center algorithms
- Decomposable multi-parameter matroid optimization problems.
- A new contraction technique with applications to congruency-constrained cuts
- A combinatorial algorithm for the ordered 1-median problem on cactus graphs
- Assigning weights to minimize the covering radius in the plane
- Building bridges between convex regions
- When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
- Selection in monotone matrices and computing k th nearest neighbors
- The multi-weighted spanning tree problem
- Title not available (Why is that?)
- Bisecting three classes of lines
- Repetitive hidden-surface-removal for polyhedral scenes
- Optimal algorithms for geometric centers and depth
- CYLINDRICAL HIERARCHY FOR DEFORMING NECKLACES
- Generalized max flows and augmenting paths
- Integrality in the multinetwork min‐cost equal‐flow problem
- A deterministic algorithm for the three-dimensional diameter problem
- Point location in zones of \(k\)-flats in arrangements
- Sigma-local graphs
- Optimization with additional variables and constraints
- EFFICIENT ALGORITHMS FOR THE OPTIMAL-RATIO REGION DETECTION PROBLEMS IN DISCRETE GEOMETRY WITH APPLICATIONS
- Algorithms and complexity analysis for some flow problems
- Locating an obnoxious line among planar objects
- Title not available (Why is that?)
- Guarding a terrain by two watchtowers
- Intersecting disks using two congruent disks
- Intersecting disks using two congruent disks
- An efficient algorithm for the proximity connected two center problem
- Minimizing Distance-to-Sight in Polygonal Domains
- Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications
- Interval finding and its application to data mining
- Efficient algorithms for the sum selection problem and \(k\) maximum sums problem
- On reverse shortest paths in geometric proximity graphs
- Minimizing the maximum moving cost of interval coverages
- Faster algorithms for largest empty rectangles and boxes
- On approximating partial scenario set cover
- On minimum and maximum spanning trees of linearly moving points
- Almost optimal algorithms for diameter-optimally augmenting trees
- Optimal parametric search on graphs of bounded tree-width
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)
