Minimizing the sum cost in linear extensions of a poset

DOI10.1007/S10878-009-9237-6zbMATH Open1213.90274OpenAlexW1994355374MaRDI QIDQ630194FDOQ630194

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

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

zbMATH Keywords

approximationpartially ordered setpolynomial algorithm

Mathematics Subject Classification ID

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

Cites Work

• Optimal Linear Extensions by Interchanging Chains
• Minimizing Setups for Cycle-Free Ordered Sets
• Minimizing bumps in linear extensions of ordered sets
• NP-completeness properties about linear extensions
• Title not available (Why is that?)
• 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
• The Jump Number of Dags and Posets: An Introduction

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)