Sorting under Partial Information with Optimal Preprocessing Time via Unified Bound Heaps
Daniel Rutschmann · 2026
Read Sorting under Partial Information with Optimal Preprocessing Time via Unified Bound Heaps by Daniel Rutschmann (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-12653.txt.
Description
Daniel Rutschmann closes the sorting under partial information problem with tight bounds. Fredman posed it in 1972: preprocess a directed acyclic graph so its vertices sort fast. Sorting time scales with the log of the number of valid orders. Prior work needed slower preprocessing. Rutschmann achieves linear preprocessing time and log-scale sorting time. A new fast heap data structure drives the result. The heap meets the unified bound, known from dictionaries and binary search trees. It may interest theorists beyond this problem.
Catalog record
| CREATOR | Daniel Rutschmann |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64071 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.12653