Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems

DOI10.1016/S0304-3975(96)00212-5zbMath0893.68080MaRDI QIDQ1389649

Sandeep Sen

Publication date: 30 June 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

parallel algorithm; decision problem; parallel algebraic decision tree model

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The average-case parallel complexity of sorting
• Parallel triangulation of a polygon in two calls to the trapezoidal map
• Parallel computational geometry
• Optimal randomized parallel algorithms for computational geometry
• Optimal, output-sensitive algorithms for constructing planar hulls in parallel
• Lower bounds for maximal and convex layers problems
• The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
• Parallel Merge Sort
• Tight Comparison Bounds on the Complexity of Parallel Sorting
• The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• A Lower Bound to Finding Convex Hulls
• Lower bounds for algebraic decision trees
• Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems
• Multidimensional Searching Problems
• The log-star revolution
• A perfect parallel dictionary