Fragile complexity of comparison-based algorithms

DOI10.4230/LIPICS.ESA.2019.2MaRDI QIDQ5075734zbMATH OpenOpenAlexFDO

Authors Peyman Afshani, Rolf Fagerberg, David Hammer, Riko Jacob, Irina Kostitsyna, Ulrich Meyer, Manuel Penschuck, Nodari Sitchinava

Publication date 11 May 2022

Full work available at URL https://arxiv.org/abs/1901.02857

zbMATH Keywords

algorithmslower boundscomparison based algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Fragile complexity of adaptive algorithms
• scientific article; zbMATH DE number 1515321
• Reliable minimum finding comparator networks

Cites work

• scientific article; zbMATH DE number 3338920 (Why is no real title available?)
• A Method of Constructing Selection Networks with O(\log n) Depth
• Comparator networks for binary heap construction
• Constructing sorting networks from k-sorters
• Expander graphs and their applications
• Fragile complexity of comparison-based algorithms
• Improved sorting networks with O(log N) depth
• Lower Bounds on Merging Networks
• Parallel Merge Sort
• Selection Networks
• Sorting in \(c \log n\) parallel steps
• Sorting networks of logarithmic depth, further simplified
• Tail bounds for sums of geometric and exponential variables
• The periodic balanced sorting network
• Zig-zag sort

Cited in

(2)

• Fragile complexity of comparison-based algorithms
• Weakly adaptive comparison searching

This page was built for publication: Fragile complexity of comparison-based algorithms

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