摘要
设Ｐ＝（Ｘ，≤）是一个半序集．本文在关于碰撞数的深度贪婪算法的基础上，直接证明了对任意的Ｐ存在一个最优的ＤＬＧ扩张；给出了ＤＬＧ半序集的定义，并证明了半序集Ｐ是ＤＬＧ半序集的一个充分条件；最后给出了ＤＬＧ扩张算法．
Let P= (X,≤) be an ordered set, based on the depth-greedy algorithm with respect to the bump number, a more restricted algorithm called depth-layer-greedy algorithm (DLG algorithm) is introduced. It is shown directly that there always exists an optimal extension in the set of extensions obtained by DLG algorithm. An ordered set P is called a DLG order if all DLG extensions of P is optimal.A sufficient condition in terms of forbidden suborders for an ordered set to be a DLG order is given. An algorithm to construct a DLG extension of ordered sets are included.
出处
《高校应用数学学报（A辑）》
CSCD
北大核心
1994年第4期435-442,共8页
Applied Mathematics A Journal of Chinese Universities(Ser.A)
关键词
半序集
碰撞数
深度贪婪算法
Ordered Set
Bump Number
Linear Extension
DLG Extension
Algorithm.
