Minimizing bumps in linear extensions of ordered sets

DOI10.1007/BF00403405zbMATH Open0595.06004OpenAlexW1983875646WikidataQ39753279 ScholiaQ39753279MaRDI QIDQ1077441FDOQ1077441

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

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

zbMATH Keywords

algorithmslinearizationjump numberfinite partially ordered set

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (18)

• Minimizing the sum cost in linear extensions of a poset
• Greedy linear extensions for minimizing bumps
• Title not available (Why is that?)
• Computing the bump number is easy
• Computing the bump number with techniques from two-processor scheduling
• The setup polyhedron of series-parallel posets
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)