Chinese Quarterly Journal of Mathematics ›› 1988, Vol. 3 ›› Issue (3): 33-42.
Previous Articles Next Articles
Received:
Online:
Published:
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.
闻振卫. 关于序集碰撞数问题深度贪心算法的最优性[J]. Chinese Quarterly Journal of Mathematics, 1988, 3(3): 33-42.
/ Recommend
URL: https://sxjk.magtechjournal.com/EN/
https://sxjk.magtechjournal.com/EN/Y1988/V3/I3/33