Chinese Quarterly Journal of Mathematics ›› 1988, Vol. 3 ›› Issue (3): 33-42.

Previous Articles     Next Articles

关于序集碰撞数问题深度贪心算法的最优性

  


  1. 苏州大学数学系
  • Received:1987-02-28 Online:1988-09-30 Published:2026-03-31

Abstract: Let  L=x₁…x,be  a  linear  extension  of  a  poset  P.Call(x,x+1)a  bump of L  if  x₁<x+1(P).The  number   of  bumps   in L  is denoted  by  B(L).  A  linear  extension  L*of  P   is  optimal  if  B(L*)=min{B(L):L  is  a  linear  extension   of  P},Fishburn   and   Gehrlein   conjectured   that,for  any   poset  P, there  exists  an  optimallinear  extension  gnerated  by  an  algorithm  which  is  greedy  with  respect  to  the  depth.In  this  paper,we  prove  that  this
conjecture  is  true  and  that  if  a  poset  P  is  N-free,then  all  its  linear  extensions  generated  by  this  algorithm  are  optimal.