Minimizing bumps in linear extensions of ordered sets

DOI10.1007/BF00403405zbMath0595.06004OpenAlexW1983875646WikidataQ39753279 ScholiaQ39753279MaRDI QIDQ1077441

William V. Gehrlein, Peter C. Fishburn

Publication date: 1986

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00403405

zbMATH Keywords

algorithmslinearizationjump numberfinite partially ordered set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06)

Related Items

Generating linear extensions of posets by transpositions, Greedy posets for the bump-minimizing problem, Computing the bump number is easy, Computing the bump number with techniques from two-processor scheduling, Minimizing bumps for posets of width two, The setup polyhedron of series-parallel posets, Minimizing bumps in ordered sets by substitution decomposition, Minimizing the maximum bump cost in linear extensions of a poset, Minimizing the sum cost in linear extensions of a poset, The connection between the bump number problem and flow-shop scheduling with precedence constraints, A comparison of algorithms for minimizing bumps in linear extensions of partial orders

Cites Work

• Unnamed Item
• Minimizing setups in ordered sets of fixed width
• On the size of jump-critical ordered sets
• Jump number problem: The role of matroids
• Minimizing the jump number for partially ordered sets: A graph-theoretic approach
• Interval graphs and interval orders
• Greedy linear extensions to minimize jumps
• On finding the jump number of a partial order by substitution decomposition
• A comparison of algorithms for minimizing bumps in linear extensions of partial orders
• Semiorders and a Theory of Utility Discrimination
• Optimal Linear Extensions by Interchanging Chains
• Examples of Jump-Critical Ordered Sets
• An Experimental Investigation and Comparative Evaluation of Production Line Balancing Techniques