Minimizing the maximum bump cost in linear extensions of a poset

DOI10.1007/S10878-012-9456-0zbMATH Open1401.90201OpenAlexW1991199948MaRDI QIDQ385489FDOQ385489

Biao Wu, Longcheng Liu, Enyu Yao

Publication date: 2 December 2013

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

Full work available at URL: https://doi.org/10.1007/s10878-012-9456-0

Recommendations

• Minimizing the sum cost in linear extensions of a poset
• Minimizing bumps in linear extensions of ordered sets
• Minimizing bumps for posets of width two
• Greedy linear extensions for minimizing bumps
• Computing the bump number with techniques from two-processor scheduling

zbMATH Keywords

optimizationpolynomial algorithmposetlinear extension

Mathematics Subject Classification ID

Partial orders, general (06A06) Combinatorial optimization (90C27) 2-person games (91A05)

Cites Work

• Minimizing Setups for Cycle-Free Ordered Sets
• Minimizing the jump number for partially ordered sets: A graph-theoretic approach
• Minimizing bumps in linear extensions of ordered sets
• Computing the bump number is easy
• Computing the bump number with techniques from two-processor scheduling
• On minimizing the jump number for interval orders
• A polynomially solvable case of optimal linear extension problem of a poset
• Minimizing the sum cost in linear extensions of a poset

Cited In (3)

• Greedy linear extensions for minimizing bumps
• \(N\)-extendible posets, and how to minimize total weighted completion time
• Maximizing a correlational ratio for linear extensions of posets

This page was built for publication: Minimizing the maximum bump 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 Q385489)