Entropy and sorting.

DOI10.1006/jcss.1995.1077zbMath1294.68069OpenAlexW4213266528MaRDI QIDQ960517

Jeong Han Kim, Jeffry Kahn

Publication date: 21 December 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1995.1077

zbMATH Keywords

polynomial time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Measures of information, entropy (94A17)

Related Items (16)

Generalizing Körner's graph entropy to graphons ⋮ Sorting probability for large Young diagrams ⋮ Sorting under partial information (without the ellipsoid algorithm). ⋮ Asymptotics of the number of standard Young tableaux of skew shape ⋮ Some bounds of weighted entropies with augmented Zagreb index edge weights ⋮ ``Cone-free primal-dual path-following and potential-reduction polynomial time interior-point methods ⋮ Linear extensions and comparable pairs in partial orders ⋮ Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets ⋮ Poset entropy versus number of linear extensions: the width-2 case. ⋮ A note on average-case sorting ⋮ Sorting and Selection with Random Costs ⋮ Communication Lower Bounds Via the Chromatic Number ⋮ Minimum entropy coloring ⋮ Preprocessing Ambiguous Imprecise Points ⋮ On Generalized Comparison-Based Sorting Problems ⋮ Balanced pairs in partial orders

This page was built for publication: Entropy and sorting.