Minimizing the maximum bump cost in linear extensions of a poset

DOI10.1007/s10878-012-9456-0zbMath1401.90201OpenAlexW1991199948MaRDI QIDQ385489

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

zbMATH Keywords

optimizationposetpolynomial algorithmlinear extension

Mathematics Subject Classification ID

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

Cites Work

• A polynomially solvable case of optimal linear extension problem of a poset
• Minimizing the sum cost in linear extensions of a poset
• 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
• Minimizing Setups for Cycle-Free Ordered Sets