Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values

DOI10.1006/JAGM.1993.1018MaRDI QIDQ4696645zbMATH OpenOpenAlexWikidataFDO

Authors Omer Berkman, Baruch Schieber, Uzi Vishkin

Publication date 29 June 1993

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/c87671177ebdc6b8f955a82d1e3e60dbaef22b3f

zbMATH Keywords

triangulationbinary treeall nearest smaller valuespreorderCRCW PRAMpostorderinorderrange minimum

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Distributed algorithms (68W15)

Recommendations

• Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm
• New algorithms for the LCA problem and the binary tree reconstruction problem
• Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs
• Triply-Logarithmic Parallel Upper and Lower Bounds for Minimum and Range Minima over Small Domains

Cited in

(39)

• Space efficient data structures for nearest larger neighbor
• An O(n 2logn) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane
• A work-time optimal algorithm for computing all string covers
• Parallel algorithms on interval graphs
• Faster entropy-bounded compressed suffix trees
• Optimal parallel algorithms for forest and term matching
• Space efficient data structures for nearest larger neighbor
• Dominance made simple
• Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs
• On finding fundamental cut sets
• ANSV problem on BSRs
• Space-efficient data structure for next/previous larger/smaller value queries
• Fast algorithms for single and multiple pattern Cartesian tree matching
• Parallel range minima on coarse grained multicomputers
• Encoding Nearest Larger Values
• All nearest smallers made simple
• Finding patterns and periods in Cartesian tree matching
• A simple algorithm for replacement paths problem
• The number of repetitions in 2D-strings
• Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs
• Parallel maximum independent set in convex bipartite graphs
• New algorithms for the LCA problem and the binary tree reconstruction problem
• Almost fully-parallel parentheses matching
• Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm
• Parallel algorithms for separable permutations
• Combined data structure for previous- and next-smaller-values
• Space-efficient parallel construction of succinct representations of suffix tree topologies
• Space-efficient data structure for next/previous larger/smaller value queries
• Parallel vertex colouring of interval graphs
• An O(log log n) algorithm to compute the kernel of a polygon
• Optimal parallel algorithms for rectilinear link-distance problems
• Algorithms for testing occurrences of length 4 patterns in permutations
• Encoding nearest larger values
• Randomized range-maxima in nearly-constant parallel time
• Fast parallel string prefix-matching
• An efficient parallel algorithm for building the separating tree
• Fast parallel algorithms for the maximum empty rectangle problem.
• An optimal parallel algorithm for computing a near-optimal order of matrix multiplications
• Time-space tradeoffs for all-nearest-larger-neighbors problems

This page was built for publication: Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values

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