Minimizing bumps in ordered sets by substitution decomposition

DOI10.1016/0012-365X(89)90328-2MaRDI QIDQ1122595zbMATH OpenFDO

Authors George Steiner

Publication date 1989

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(89)90328-2

zbMATH Keywords

autonomous subsetlinear extensionminimal number of bumps

Mathematics Subject Classification ID

Total orders (06A05) Partial orders, general (06A06)

Review text

Consider a partially ordered set P of n elements. A linear extension \(x_ 1x_ 2...x_ n\) of P has a bump whenever \(x_ i<x_{i+1}\) in P. A decomposition theorem is presented for the problem of finding a linear extension of P with the minimal number of bumps.

Recommendations

• Minimizing bumps for posets of width two
• Minimizing bumps in linear extensions of ordered sets
• A comparison of algorithms for minimizing bumps in linear extensions of partial orders
• Computing the bump number is easy
• Greedy linear extensions for minimizing bumps

Cites work

• A comparison of algorithms for minimizing bumps in linear extensions of partial orders
• A Fast Algorithm for the Decomposition of Graphs and Posets
• Computing the bump number is easy
• Greedy posets for the bump-minimizing problem
• scientific article; zbMATH DE number 6157242 (Why is no real title available?)
• Minimizing bumps for posets of width two
• Minimizing bumps in linear extensions of ordered sets
• Optimal Linear Extensions by Interchanging Chains

Cited in

(7)

• Minimizing bumps in linear extensions of ordered sets
• Computing the bump number is easy
• Minimizing bumps for posets of width two
• A comparison of algorithms for minimizing bumps in linear extensions of partial orders
• Cross-series-parallel digraphs
• scientific article; zbMATH DE number 800166 (Why is no real title available?)
• The connection between the bump number problem and flow-shop scheduling with precedence constraints

This page was built for publication: Minimizing bumps in ordered sets by substitution decomposition

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