Minimizing the sum cost in linear extensions of a poset

DOI10.1007/S10878-009-9237-6MaRDI QIDQ630194zbMATH OpenOpenAlexFDO

Authors Longcheng Liu, Biao Wu, Enyu Yao

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

approximationpartially ordered setpolynomial algorithm

Mathematics Subject Classification ID

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

Recommendations

• Minimizing the maximum bump cost in linear extensions of a poset
• Generating Linear Extensions Fast
• The poset scheduling problem
• Greedy linear extensions to minimize jumps
• Average relational distance in linear extensions of posets

Cites work

• scientific article; zbMATH DE number 3641455 (Why is no real title available?)
• A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
• Greedy posets for the bump-minimizing problem
• Minimizing Setups for Cycle-Free Ordered Sets
• Minimizing bumps in linear extensions of ordered sets
• NP-completeness properties about linear extensions
• On minimizing jumps for ordered sets
• Optimal Linear Extensions by Interchanging Chains
• The Jump Number of Dags and Posets: An Introduction
• The jump number of Z-free ordered sets

Cited in

(3)

• A polynomially solvable case of optimal linear extension problem of a poset
• \(N\)-extendible posets, and how to minimize total weighted completion time
• Minimizing the maximum bump cost in linear extensions of a poset

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q630194)