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

CREATORDaniel Rutschmann
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE64071
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.12653

Browse the full library · About the Tower of Babel