2020/08/24 by Jawaherul Md. Alam, Michael A. Bekos, Alam, Jawaherul Md. +7
Business, Management and Accounting · Economics, Econometrics and Finance · #Consumer Market Behavior and Pricing #Data Structures and Algorithms (cs.DS) #Economic theories and models #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2008.10336
openalex publication_date 2020/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the queue number of posets in terms of their width, that is, the maximum number of pairwise incomparable elements. A long-standing conjecture of Heath and Pemmaraju asserts that every poset of width w has queue number at most w. The conjecture has been confirmed for posets of width w=2 via so-called lazy linear extension. We extend and thoroughly analyze lazy linear extensions for posets of width w > 2. Our analysis implies an upper bound of (w-1)2 +1 on the queue number of width-w posets, which is tight for the strategy and yields an improvement over the previously best-known bound. Further, we provide an example of a poset that requires at least w+1 queues in every linear extension, thereby disproving the conjecture for posets of width w > 2.