Minimizing the maximum bump cost in linear extensions of a poset

CORC > 厦门大学 > 信息技术－已发表论文

	Minimizing the maximum bump cost in linear extensions of a poset
	Wu, Biao ; Liu, Longcheng ; Yao, Enyu ; Liu LC(刘龙城)
刊名	http://dx.doi.org/10.1007/s10878-012-9456-0
	2013
关键词	ORDERED SETS NUMBER
英文摘要	National Nature Science Foundation of China [10971191, 11001232]; Fundamental Research Funds for the Central Universities [2010121004]; Department of Education of Zhejiang Province of China [Y200909535]; 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.
语种	英语
出版者	SPRINGER
内容类型	期刊论文
源URL	[http://dspace.xmu.edu.cn/handle/2288/92538]
专题	信息技术－已发表论文
推荐引用方式 GB/T 7714	Wu, Biao,Liu, Longcheng,Yao, Enyu,et al. Minimizing the maximum bump cost in linear extensions of a poset[J]. http://dx.doi.org/10.1007/s10878-012-9456-0,2013.
APA	Wu, Biao,Liu, Longcheng,Yao, Enyu,&刘龙城.(2013).Minimizing the maximum bump cost in linear extensions of a poset.http://dx.doi.org/10.1007/s10878-012-9456-0.
MLA	Wu, Biao,et al."Minimizing the maximum bump cost in linear extensions of a poset".http://dx.doi.org/10.1007/s10878-012-9456-0 (2013).