Minimizing the sum cost in linear extensions of a poset

DOI10.1007/s10878-009-9237-6zbMath1213.90274OpenAlexW1994355374MaRDI QIDQ630194

Longcheng Liu, Enyu Yao, Biao Wu

Publication date: 17 March 2011

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-009-9237-6

zbMATH Keywords

approximationpolynomial algorithmpartially ordered set

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Combinatorial optimization (90C27)

Related Items (1)

Minimizing the maximum bump cost in linear extensions of a poset

Cites Work

• NP-completeness properties about linear extensions
• Minimizing bumps in linear extensions of ordered sets
• A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
• Greedy posets for the bump-minimizing problem
• On minimizing jumps for ordered sets
• The jump number of Z-free ordered sets
• Optimal Linear Extensions by Interchanging Chains
• The Jump Number of Dags and Posets: An Introduction
• Minimizing Setups for Cycle-Free Ordered Sets
• Unnamed Item

This page was built for publication: Minimizing the sum cost in linear extensions of a poset