On generalized comparison-based sorting problems

DOI10.1007/978-3-642-40273-9_12MaRDI QIDQ2848974zbMATH OpenOpenAlexFDO

Authors Jean Cardinal, Samuel Fiorini

Publication date 13 September 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-40273-9_12

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• Entropy and sorting.
• Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime
• An efficient algorithm for partial order production
• An efficient algorithm for partial order production

Cites work

• scientific article; zbMATH DE number 1003302 (Why is no real title available?)
• scientific article; zbMATH DE number 108389 (Why is no real title available?)
• scientific article; zbMATH DE number 3468645 (Why is no real title available?)
• scientific article; zbMATH DE number 3596259 (Why is no real title available?)
• scientific article; zbMATH DE number 1354145 (Why is no real title available?)
• Algorithms for the Generalized Sorting Problem
• An efficient algorithm for partial order production
• Automata, Languages and Programming
• Balanced pairs in partial orders
• Balancing extensions via Brunn-Minkowski
• Balancing pairs and the cross product conjecture
• Bounds on Optimal Merge Performance, and a Strategy for Optimality
• Counting linear extensions
• Entropy and sorting.
• Entropy splitting for antiblocking corners and perfect graphs
• Every poset has a central element
• How good is the information theory bound in sorting?
• Matching Nuts and Bolts in O(n log n) Time
• On the Complexity of Partial Order Productions
• Producing posets
• Searching in 2-dimensional partial orders
• Searching in Trees, Series-Parallel and Interval Orders
• Sorting and Recognition Problems for Ordered Sets
• Sorting and selection in posets
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Information-Theoretic Bound is Good for Merging

Cited in

(13)

• An optimal algorithm for sorting in trees
• Comparing algorithms for sorting with t stacks in series
• scientific article; zbMATH DE number 5556016 (Why is no real title available?)
• New results in minimum-comparison sorting
• scientific article; zbMATH DE number 22189 (Why is no real title available?)
• A generalized insertion algorithm for the seriation problem
• Fast and simple sorting using partial information
• scientific article; zbMATH DE number 1555930 (Why is no real title available?)
• Sorting under forbidden comparisons
• On the optimality of tape merge of two lists with similar size
• scientific article; zbMATH DE number 3874633 (Why is no real title available?)
• On instance-optimal algorithms for a generalization of nuts and bolts and generalized sorting
• Generalized sorting with predictions

This page was built for publication: On generalized comparison-based sorting problems

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