Recursively divisible problems

DOI10.1007/BFB0009494MaRDI QIDQ6487438zbMATH OpenFDO

Authors Rolf Niedermeier

Publication date 25 January 2023

Full work available at URL https://doi.org/10.1007/BFB0009494

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Communication complexity, information complexity (68Q11)

Recommendations

• Divisible task scheduling -- concept and verification: Special issue on task scheduling problems for parallel and distributed systems
• How evenly should one divide to conquer quickly?
• Parallel algorithms for partitioning sorted sets and related problems
• scientific article; zbMATH DE number 5842467
• Parallel complexity of sorting problems

Cites work

• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• A complexity theory of efficient parallel algorithms
• A practical hierarchical model of parallel computation. I: The model
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Communication complexity of PRAMs
• Cubesort: A parallel algorithm for sorting N data items with S-sorters
• New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P
• On uniform circuit complexity
• Tight Bounds on the Complexity of Parallel Sorting

This page was built for publication: Recursively divisible problems

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