Minimizing the sum cost in linear extensions of a poset |
| |
Authors: | Longcheng Liu Biao Wu Enyu Yao |
| |
Institution: | 1.School of Mathematical Sciences,Xiamen University,Xiamen,P.R. China;2.Department of Mathematics,Zhejiang University,Hangzhou,P.R. China |
| |
Abstract: | 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 in L whenever x≤yin P. In this paper, we assign each pair of elements x,y∈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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|