科研之友
微信
新浪微博
Facebook
分享链接
摘要
A linear extension of a poset P=(X,a parts per thousand(0)) is a permutation x (1),x (2),aEuro broken vertical bar,x (|X|) of X such that i < j whenever x (i) a parts per thousand(0)x (j) . For a given poset P=(X,a parts per thousand(0)) and a cost function c(x,y) defined on XxX, we want to find a linear extension of P such that maximum cost is as small as possible. For the general case, it is NP-complete. In this paper we consider the linear extension problem with the assumption that c(x,y)=0 whenever x and y are incomparable. First, we prove the discussed problem is polynomially solvable for a special poset. And then, we present a polynomial algorithm to obtain an approximate solution.
