Minimizing the maximum bump cost in linear extensions of a poset

Author： Wu Biao   Liu Longcheng   Yao Enyu  

Publisher： Springer Publishing Company

ISSN： 1382-6905

Source： Journal of Combinatorial Optimization, Vol.26, Iss.3, 2013-10, pp. : 509-519

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

A linear extension of a poset P=(X,≺) is a permutation x 1,x 2,…,x |X| of X such that i<j whenever x i ≺x j . For a given poset P=(X,≺) and a cost function c(x,y) defined on X×X, 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.

Related content

Minimizing the sum cost in linear extensions of a poset

By Liu Longcheng   Wu Biao   Yao Enyu  

Journal of Combinatorial Optimization, Vol. 21, Iss. 2, 2011-02 ,pp. : 247-253 (7)

Springer Publishing Company

Access to resources Recommend Favorite

Maximum Monoreflections and Essential Extensions

By Hager A.W.  

Applied Categorical Structures, Vol. 9, Iss. 5, 2001-09 ,pp. : 517-523 (7)

Springer Publishing Company

Access to resources Recommend Favorite

A polynomially solvable case of optimal linear extension problem of a poset

By Wu Biao   Yao Enyu   Liu Longcheng  

Journal of Combinatorial Optimization, Vol. 20, Iss. 4, 2010-11 ,pp. : 422-428 (7)

Springer Publishing Company

Access to resources Recommend Favorite

Triangulating Planar Graphs While Minimizing the Maximum Degree

By Kant G.   Bodlaender H.L.  

Information and Computation, Vol. 135, Iss. 1, 1997-05 ,pp. : 1-14 (14)

Academic Press

Access to resources Recommend Favorite

Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree

By Asahiro Yuichi  

Journal of Combinatorial Optimization, Vol. 22, Iss. 1, 2011-07 ,pp. : 78-96 (19)

Springer Publishing Company

Access to resources Recommend Favorite