Sorting under forbidden comparisons

DOI10.4230/LIPICS.SWAT.2016.22MaRDI QIDQ5369524zbMATH OpenOpenAlexFDO

Authors Indranil Banerjee, Dana Richards

Publication date 17 October 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.SWAT.2016.22

zbMATH Keywords

complexityrandom graphssorting

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime
• On generalized comparison-based sorting problems
• On sorting in the presence of erroneous information
• Entropy and sorting.

Cited in

(6)

• Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime
• Generalized sorting with predictions revisited
• Generalized sorting with predictions
• Algorithms for the generalized poset sorting problem
• An algorithm for bichromatic sorting with polylog competitive ratio
• An optimal algorithm for sorting in trees

This page was built for publication: Sorting under forbidden comparisons

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