科研之友
微信
新浪微博
Facebook
分享链接
摘要
A linear extension problem is defined as follows: Given a poset P=(E,<=), we want to find a linear order L such that x <= y signy in L whenever x <= y in P. In this paper, we assign each pair of elements x,y is an element of E with a cost, and to find a linear extension of P with the minimum sum cost. For the general case, it is NP-complete and we present a greedy approximation algorithm which can be finished in polynomial time. Also we consider a special case which can be solved in polynomial time.
