On generalized comparison-based sorting problems

DOI10.1007/978-3-642-40273-9_12zbMATH Open1394.68105OpenAlexW428405241MaRDI QIDQ2848974FDOQ2848974

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

Recommendations

• Entropy and sorting.
• Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime
• Sorting under partial information (without the ellipsoid algorithm)
• An efficient algorithm for partial order production
• An efficient algorithm for partial order production

Mathematics Subject Classification ID

Searching and sorting (68P10)

Cites Work

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

Cited In (10)

• Comparing algorithms for sorting with \(t\) stacks in series
• Title not available (Why is that?)
• New results in minimum-comparison sorting
• Title not available (Why is that?)
• A generalized insertion algorithm for the seriation problem
• Sorting under forbidden comparisons
• Title not available (Why is that?)
• On the optimality of tape merge of two lists with similar size
• Title not available (Why is that?)
• Improved average complexity for comparison-based sorting

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)