摘要
设Ｐ＝（Ｘ，≤）是一个半序集，Ｈａｂｌｂ等人与Ａ，Ｓｃｈａｆｆｅｒ同时证明了求Ｐ关于碰撞数的最优扩张的问题是Ｐ－问题；本文给出了一个求具有最小碰撞数的半序集的线性扩张的多项式算法。
Let p =(x,≤)be an ordered set.A. Schaffer and Habib and others have proved thatthe problem finding optimal extensions with respect to the bump number of the ordered set P is P-problem at the same time. A polynomial algorithm to find a linear extension of an ordered setwhich has the minimum bumps is presented.
出处
《南昌大学学报（理科版）》
CAS
1995年第2期154-157,共4页
Journal of Nanchang University(Natural Science)
关键词
碰撞数
线性扩张
序集
半序集
多项式算法
bump number ,linear extension algorithm,ordered set,combinatorial optimization
