论文标题
lazy队列posets的布局
Lazy Queue Layouts of Posets
论文作者
论文摘要
我们根据其宽度（即成对无与伦比的元素的最大数量）研究了POSET的队列数量。长期以来的荒地和彭马拉朱（Pemmaraju）的猜想断言，每个宽度的poset w w w w。通过所谓的懒惰线性扩展，已经确认了宽度W = 2的POSET的猜想。 我们扩展并彻底分析了宽度w> 2的POSET的懒惰线性扩展。我们的分析意味着$（W-1）^2 +1 $的上限在宽度-W Posets的队列数量上，这对于该策略来说很紧，并且比以前最不知名的界限进行了改进。此外，我们提供了一个poset的示例，该poset在每个线性扩展中至少需要W+1个队列，从而反驳了宽度w> 2的posets的猜想。
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.
