Minimizing bumps in linear extensions of ordered sets

DOI10.1007/BF00403405MaRDI QIDQ1077441zbMATH OpenOpenAlexWikidataFDO

Authors Peter Fishburn, William V. Gehrlein

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

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

Recommendations

• Minimizing bumps for posets of width two
• Computing the bump number is easy
• Computing the bump number with techniques from two-processor scheduling
• A comparison of algorithms for minimizing bumps in linear extensions of partial orders
• Minimizing bumps in ordered sets by substitution decomposition

Cites work

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

Cited in

(18)

• Minimizing the sum cost in linear extensions of a poset
• Greedy linear extensions for minimizing bumps
• scientific article; zbMATH DE number 27746 (Why is no real title available?)
• Computing the bump number is easy
• Computing the bump number with techniques from two-processor scheduling
• The setup polyhedron of series-parallel posets
• scientific article; zbMATH DE number 221764 (Why is no real title available?)
• Minimals Plus: an improved algorithm for the random generation of linear extensions of partially ordered sets
• Generating linear extensions of posets by transpositions
• The connection between the bump number problem and flow-shop scheduling with precedence constraints
• Minimizing bumps in ordered sets by substitution decomposition
• Minimizing bumps for posets of width two
• Greedy posets for the bump-minimizing problem
• The jump number of Z-free ordered sets
• Greedy linear extensions to minimize jumps
• A comparison of algorithms for minimizing bumps in linear extensions of partial orders
• scientific article; zbMATH DE number 800166 (Why is no real title available?)
• Minimizing the maximum bump cost in linear extensions of a poset

This page was built for publication: Minimizing bumps in linear extensions of ordered sets

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