Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
From MaRDI portal
Publication:4696645
DOI10.1006/jagm.1993.1018zbMath0782.68031OpenAlexW2059245171WikidataQ55895983 ScholiaQ55895983MaRDI QIDQ4696645
Baruch Schieber, Uzi Vishkin, Omer Berkman
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
Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Distributed algorithms (68W15)
Related Items (37)
New algorithms for the LCA problem and the binary tree reconstruction problem ⋮ ANSV problem on BSRs ⋮ Almost fully-parallel parentheses matching ⋮ An O(log log n) algorithm to compute the kernel of a polygon ⋮ An optimal parallel algorithm for computing a near-optimal order of matrix multiplications ⋮ Space efficient data structures for nearest larger neighbor ⋮ Parallel maximum independent set in convex bipartite graphs ⋮ Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs ⋮ Optimal parallel algorithms for rectilinear link-distance problems ⋮ A simple algorithm for replacement paths problem ⋮ Simultaneous encodings for range and next/previous larger/smaller value queries ⋮ All Nearest Smallers Made Simple ⋮ Encoding Nearest Larger Values ⋮ Space Efficient Data Structures for Nearest Larger Neighbor ⋮ Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs ⋮ Space-efficient data structure for next/previous larger/smaller value queries ⋮ Unnamed Item ⋮ Algorithms for testing occurrences of length 4 patterns in permutations ⋮ Encoding nearest larger values ⋮ Finding patterns and periods in Cartesian tree matching ⋮ Fast algorithms for single and multiple pattern Cartesian tree matching ⋮ An O(n 2logn) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane ⋮ Parallel algorithms on interval graphs ⋮ An efficient parallel algorithm for building the separating tree ⋮ Optimal parallel algorithms for forest and term matching ⋮ A work-time optimal algorithm for computing all string covers ⋮ Fast parallel string prefix-matching ⋮ Combined data structure for previous- and next-smaller-values ⋮ Parallel algorithms for separable permutations ⋮ Randomized range-maxima in nearly-constant parallel time ⋮ Dominance made simple ⋮ On finding fundamental cut sets ⋮ Fast parallel algorithms for the maximum empty rectangle problem. ⋮ Faster entropy-bounded compressed suffix trees ⋮ PARALLEL VERTEX COLOURING OF INTERVAL GRAPHS ⋮ PARALLEL RANGE MINIMA ON COARSE GRAINED MULTICOMPUTERS ⋮ Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies
This page was built for publication: Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
