一个求半序集的最优碰撞数扩张的多项式算法

摘要

设Ｐ＝（Ｘ，≤）是一个半序集，Ｈａｂｌｂ等人与Ａ，Ｓｃｈａｆｆｅｒ同时证明了求Ｐ关于碰撞数的最优扩张的问题是Ｐ－问题；本文给出了一个求具有最小碰撞数的半序集的线性扩张的多项式算法。